′夭天操夜夜操,3蝥你VVV,亚洲精品无码99热

前言

素?cái)?shù)這個(gè)概念人類已經(jīng)研究了上千年，但是的具體的起源卻不得而知。早在公元前300年，歐幾里得就在他的著作元素中證明了有無窮多個(gè)素?cái)?shù)，同時(shí)也證明了任何一個(gè)整數(shù)都能夠被某一個(gè)素?cái)?shù)整除。時(shí)至今日，素?cái)?shù)在計(jì)算機(jī)科學(xué)這樣一個(gè)和數(shù)學(xué)聯(lián)系緊密的學(xué)科中也有這個(gè)廣泛的應(yīng)用，比如布隆過濾器、偽隨機(jī)數(shù)、RSA加密算法等等，所以掌握素?cái)?shù)的特性以及應(yīng)用能夠幫助我們解決不少實(shí)際問題。

簡介

素?cái)?shù)（又稱質(zhì)數(shù)）是一個(gè)只能被1和它自己整除的整數(shù)，換句話說他只有兩個(gè)因數(shù)——1和它自己。比如3是一個(gè)素?cái)?shù)，因?yàn)?只能被1和3整除，但是6不是素?cái)?shù)因?yàn)樗鼙?和3整除。迄今為止發(fā)現(xiàn)的最大的素?cái)?shù)是 $2^{57885161}-1$ ，由中央密蘇里大學(xué)的數(shù)學(xué)家Curtis Cooper發(fā)現(xiàn)，大概有17,425,170位數(shù)字。

在公元前200年，古希臘數(shù)學(xué)家埃拉托色尼（Eratosthenes）創(chuàng)造了一套算法用來計(jì)算素?cái)?shù)，這就是大家熟知的埃拉托色尼篩選法（the Sieve of Eratosthenes），這是最早的用來計(jì)算素?cái)?shù)的方法。就拿100以內(nèi)素?cái)?shù)的方法來簡單介紹一下這個(gè)篩選法：

首先我們找到第一個(gè)素?cái)?shù)2，用圓圈標(biāo)出來，然后劃掉所有2的倍數(shù)4、6、8等等。然后我們找到下一個(gè)沒有被劃掉的數(shù)字（這個(gè)數(shù)字肯定不是前面更小數(shù)字的倍數(shù)），也就是3，用圓圈標(biāo)出來，再劃掉所有的3的倍數(shù)，注意這里6已經(jīng)被劃掉了，但是9可以繼續(xù)被劃掉。接下來再用圓圈標(biāo)出下一個(gè)沒有被劃掉的數(shù)字5，劃掉所有的5的倍數(shù)。如此往復(fù)，直到100的平方根10截止，所有的100以內(nèi)的素?cái)?shù)就都被圓圈圈起來了。

the Sieve of Eratosthenes

計(jì)數(shù)質(zhì)數(shù)

來看看素?cái)?shù)計(jì)算的最簡單的版本，Leetcode第204題計(jì)數(shù)質(zhì)數(shù)。

統(tǒng)計(jì)所有小于非負(fù)整數(shù) n 的質(zhì)數(shù)的數(shù)量。

示例：

輸入: 10
輸出: 4
解釋: 小于 10 的質(zhì)數(shù)一共有 4 個(gè), 它們是 2, 3, 5, 7 。

這道題通過我們?cè)谏厦娼榻B的埃拉托色尼篩選法可以很輕松的做出來，只需要?jiǎng)?chuàng)建一個(gè)小于n的數(shù)組，從索引2開始一直到Math.sqrt(n)對(duì)整個(gè)隊(duì)列進(jìn)行篩選，最后統(tǒng)計(jì)一遍整個(gè)數(shù)組里面所有的素?cái)?shù)就行了。

public int countPrimes(int n) {
    if (n <= 2) return 0;
    boolean[] primes = new boolean[n];  //創(chuàng)建整個(gè)素?cái)?shù)數(shù)組
    Arrays.fill(primes, true);      //初始化全部位素?cái)?shù)
    primes[0] = false;
    primes[1] = false;                  //劃掉0和1
    int sqrt = (int)Math.sqrt(n);       //設(shè)置上界
    for (int i = 2; i <= sqrt; i++) {
        if (!primes[i]) continue;       //不是素?cái)?shù)，可以跳過
        for (int multi = i<<1; multi < n ; multi += i){
            primes[multi] = false;      //劃掉倍數(shù)
        }
    }
    int count = 0;
    for (boolean prime : primes) {      //統(tǒng)計(jì)數(shù)組中素?cái)?shù)的數(shù)量
        if (prime) count++;
    }
    return count;
}

運(yùn)行了上面的代碼之后，執(zhí)行時(shí)間17ms，才擊敗了60%的用戶，代碼還有很大的優(yōu)化空間。我們從上一個(gè)小節(jié)的篩選法中就可以看到，我們經(jīng)常要?jiǎng)澋粢呀?jīng)被劃掉的數(shù)字，比如在劃掉了所有的2的倍數(shù)6之后，我們?cè)趧澋?的倍數(shù)的時(shí)候又劃掉了6一次，這樣就浪費(fèi)了我們的資源，能不能直接跳過6去劃掉9呢？所以這里就是需要考慮要從哪個(gè)數(shù)字開始劃數(shù)字。在劃掉2的倍數(shù)的時(shí)候，我們是劃掉2x2、2x3、2x4、2x5等等，在劃掉3的時(shí)候是劃掉3x2（在素?cái)?shù)2的那一輪已經(jīng)被劃掉了）、3x3、3x4、3x5等，在劃掉5的時(shí)候是劃掉5x2（素?cái)?shù)2的一輪已經(jīng)被劃掉了）、5x3（素?cái)?shù)3的一輪被劃掉了）、5x4（等于10x2也在素?cái)?shù)2的一輪被劃掉了）、5x5等等?，F(xiàn)在這個(gè)規(guī)律應(yīng)該十分明顯了，在劃掉素?cái)?shù)i的倍數(shù)的時(shí)候，所有比i小的數(shù)字的和i的乘積已經(jīng)被劃掉了，所以下一輪直接從i*i開始就行了，于是我們可以把上面代碼里面的multi初始化為i*i，代碼我就不貼出來了。

其實(shí)這道題還有挺多的改進(jìn)方法的，比如使用BitSet來代替boolean的數(shù)組、用false代表是位置i是質(zhì)數(shù)來縮短數(shù)組的初始化時(shí)間或者在第一個(gè)for循環(huán)里面就統(tǒng)計(jì)所有非質(zhì)數(shù)省去最后一個(gè)循環(huán)，可以用很多方法減少冗余操作的時(shí)間，不過整體最終的時(shí)間復(fù)雜度是 $O(NloglogN)$ ，第一個(gè)for循環(huán)是不可避免的，下面我們來用一些數(shù)學(xué)知識(shí)來解釋一下這個(gè)時(shí)間復(fù)雜度。

首先我們有數(shù)字n代表素?cái)?shù)的上邊界（不包含），p代表小于n的最大素?cái)?shù)，內(nèi)部循環(huán)設(shè)置false的時(shí)間是恒定的。

當(dāng)i==2時(shí)，內(nèi)部的篩除操作進(jìn)行了 $\frac{n}{2}$ 次

當(dāng)i==3時(shí)，篩除了 $\frac{n}{3}$ 次

當(dāng)i==4時(shí)，直接跳過，篩除了 $0$ 次（所有的非素?cái)?shù)都會(huì)跳過）

當(dāng)i==5時(shí)，篩除了 $\frac{n}{5}$ 次

當(dāng)i==p時(shí)，篩除了 $\frac{n}{p}$ 次

所以總體的運(yùn)行時(shí)間可以看作：

$\frac{n}{2}+\frac{n}{3}+\frac{n}{5}+...\frac{n}{p}$

等效于

$n\times(\frac{1}{2}+\frac{1}{3}+\frac{1}{5}+...\frac{1}{p})$

現(xiàn)在就是要證明

$\frac{1}{2}+\frac{1}{3}+\frac{1}{5}+...\frac{1}{p} = loglogn$

在進(jìn)行下面的證明的時(shí)候，我們需要用到調(diào)和級(jí)數(shù)、泰勒級(jí)數(shù)、歐拉乘積公式，這幾個(gè)公式的證明過程感興趣的可以自己去看看（在我的參考文檔里面，純數(shù)學(xué)部分，比寫代碼難多了），就先說我們要用到的定理。

調(diào)和級(jí)數(shù)（Harmonic series）是一個(gè)發(fā)散的無窮級(jí)數(shù)，當(dāng) $n$ 趨近于無窮大時(shí)，有一個(gè)近似公式：

$1 + \frac{1}{2} + \frac{1}{3} + ... = \sum_{i=1}^{n}\frac{1}{i} = ln(n)+\gamma$

其中 $\gamma$ 為歐拉常數(shù)， $\gamma \approx 0.57721$

泰勒級(jí)數(shù)（Taylor series）是1715年英國數(shù)學(xué)家布魯克·泰勒提出的，在零點(diǎn)的導(dǎo)數(shù)求得的泰勒級(jí)數(shù)又叫麥克勞林級(jí)數(shù)，具體的原版的公式我就不在這里貼出來了，這里只貼一個(gè)常用的泰勒級(jí)數(shù)，也就是以 $e$ 為底數(shù)的自然對(duì)數(shù)的麥克勞林序列

$ln(1-x) = -\sum_{n=1}^{\infty} \frac{x^n}{n} = -x-\frac{x^2}{2}-\frac{x^3}{3}-..-\frac{x^n}{n}$

對(duì)任意屬于 $[-1,1)$ 內(nèi)的 $x$ 都成立。左右的符號(hào)同時(shí)取反，可以得到：

$ln(1-x)^{-1} = \sum_{n=1}^{\infty} \frac{x^n}{n} = x+\frac{x^2}{2}+\frac{x^3}{3}+..+\frac{x^n}{n}$

歐拉乘積公式（Euler product）是著名的瑞士數(shù)學(xué)家歐拉于1737年在俄羅斯的圣彼得堡科學(xué)院發(fā)表的重要公式，為數(shù)學(xué)家研究素?cái)?shù)的分布奠定了基礎(chǔ)，即：

$\sum_{n} n^{-s} = \prod_{p}^1 (1-p^{-s})^{-1}$

其中n為自然數(shù)，p為素?cái)?shù)。

繼續(xù)我們的推理。

在歐拉公式中，我們?nèi)绻麑⑺械?img class="math-inline" src="https://math.jianshu.com/math?formula=s" alt="s" mathimg="1">用 $1$ 來代替就可以得到

$\sum_{n} n^{-1} = \prod_{p}^1 (1-p^{-1})^{-1}$

對(duì)兩側(cè)同時(shí)使用 $log$ 函數(shù)可以得到

$ln(\sum_{n} n^{-1}) = ln(\prod_{p}^1 (1-p^{-1})^{-1})$

簡化之后可以得到

$ln(\sum_{n} n^{-1}) = \sum_{p} ln((1-p^{-1})^{-1})$

因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=-1%20%3C%20p%5E%7B-1%7D%20%3C%201" alt="-1 < p^{-1} < 1" mathimg="1">，所以可以對(duì)上面公式的右側(cè)的每一項(xiàng)進(jìn)行泰勒展開得到

$ln((1-p^{-1})^{-1}) = \sum_{n=1}^{\infty} \frac{1}{np^{n}}$

當(dāng) $p$ 趨近于無窮大的時(shí)候，右側(cè)的公式收斂于 $\frac{1}{p}$ ，就可以得到

$ln((1-p^{-1})^{-1}) = \frac{1}{p}$

代入到原公式可以得到

$ln(\sum_{n} n^{-1}) =\sum_{p} \frac{1}{p}$

上述公式左側(cè)log內(nèi)部正好是調(diào)和級(jí)數(shù)，把調(diào)和級(jí)數(shù)的近似公式代入左側(cè)可以得到

$\sum_{p} \frac{1}{p} = ln(ln(n)+\gamma)$

忽略右邊的常數(shù) $\gamma$ 就可以得到最后的時(shí)間復(fù)雜度為 $O(nln(ln(n)))$ ，也就是 $O(nloglogn)$ 級(jí)別。

除了這個(gè)證明過程之外，在數(shù)論里面已經(jīng)有一個(gè)定理證明這個(gè)時(shí)間復(fù)雜度——Mertens' second theorem（維基百科需要科學(xué)上網(wǎng)，中文材料好像特別少）。

能夠看到這個(gè)地方已經(jīng)說明你有著超人般的毅力（還有什么比數(shù)學(xué)更令人頭疼），如果覺得上面的講解還不夠清楚或者有很多數(shù)學(xué)的細(xì)節(jié)不太理解，可以看看參考文檔。據(jù)我在網(wǎng)上查到的，還沒有任何一篇文章能夠像這篇一樣把埃拉托色尼篩選法的時(shí)間復(fù)雜度講的這么清楚的，希望能夠幫助到大家。

應(yīng)用1 哈希算法

哈希表是我們?nèi)粘ｉ_發(fā)中用的非常多的一種數(shù)據(jù)結(jié)構(gòu)，在執(zhí)行搜索、插入或者刪除的時(shí)候能夠在O(i)的時(shí)間內(nèi)完成操作，相比于二分搜索樹最快也要O(logN)的時(shí)間，性能得到極大的提高。

哈希表是利用哈希算法將鍵轉(zhuǎn)化成數(shù)組中的一個(gè)索引，直接使用這個(gè)索引地址找到或者插入元素。常用的哈希算法是通過取模操作拿到索引。比如在下面的代碼中，TABLE_SIZE是數(shù)組的大小，得到結(jié)果就是數(shù)組索引。

private int hash(int key) {
    return key % TABLE_SIZE;
}

但是在上面轉(zhuǎn)化的過程中可能會(huì)出現(xiàn)沖突，也就是兩個(gè)不同的Key通過哈希算法得到同一個(gè)索引，比如當(dāng)key為TABLE_SIZE和2*TABLE_SIZE，取模得到的值都是0，產(chǎn)生沖突，不管是索引往后順移還是使用鏈表（或者紅黑樹）都會(huì)降低哈希表的性能。數(shù)組的長度越小，需要存儲(chǔ)的數(shù)值越多，就越容易發(fā)生沖突，為了盡量減小沖突，通常對(duì)素?cái)?shù)取模。

比如說現(xiàn)在有一組比較特殊的鍵key=[0,3,6...99]，并且hashTable的大小是m=12，因?yàn)?code>3是12的因數(shù)，所以所有的3的倍數(shù)都會(huì)被哈希到3的倍數(shù)的位置中

[0,15,30...]哈希到0
[3,18,33...]哈希到3
[6,21,36...]哈希到6
[9,24,39...]哈希到9
[12,27,42...]哈希到0

如此類推可知雖然我們表的大小是12，但是所有的數(shù)字只哈希到了0,3,6,9四個(gè)位置，明顯不是我們想要的。如果我們把表的大小換成素?cái)?shù)13，那么就不會(huì)有這么多的沖突。用素?cái)?shù)的最大好處是可以盡量避免把有相同特性的元素（在這里特性是所有的鍵都能被3整除）放到集中的幾個(gè)位置中。

雖說用素?cái)?shù)取模能夠減小沖突，但是前提是所有的鍵并不是完全隨機(jī)而是有一定特點(diǎn)的。對(duì)于完全隨機(jī)的輸入，即使用素?cái)?shù)也不能減少?zèng)_突。

應(yīng)用2 RSA加密算法

RSA（Rivest–Shamir–Adleman）是最早的公鑰密碼系統(tǒng)之一，被廣泛用于安全數(shù)據(jù)傳輸。在這樣的密碼系統(tǒng)中，加密密鑰是公共的，而解密密鑰卻是私密的。在RSA中，這種不對(duì)稱性是基于對(duì)兩個(gè)大質(zhì)數(shù)乘積進(jìn)行因式分解的實(shí)踐困難，即“因式分解問題”。縮寫詞RSA由Ron Rivest，Adi Shamir和Leonard Adleman的姓氏的首字母組成，他們于1977年首次公開描述了該算法。Clifford Cocks，在英國情報(bào)局政府通信總部（GCHQ）工作的英國數(shù)學(xué)家。于1973年開發(fā)了一個(gè)等效系統(tǒng)，但直到1997年才解密。

RSA算法是用兩個(gè)大質(zhì)數(shù)以及一個(gè)輔助值創(chuàng)建一個(gè)公共密鑰發(fā)布出去。這兩個(gè)素?cái)?shù)必須保密。任何人都可以使用公共密鑰對(duì)信息進(jìn)行加密，但是只有知道質(zhì)數(shù)的人才能對(duì)郵件進(jìn)行解碼。破解RSA加密被稱為RSA問題。如果使用足夠大的質(zhì)數(shù)作為密鑰，那么當(dāng)前還沒有方法可以使破解RSA加密。RSA算法的可行性證明涉及到了費(fèi)馬定律，這里就不多講了，這里只是簡單講解一下RSA算法的工作過程。

RSA算法涉及到4個(gè)步驟：生成密鑰、發(fā)布密鑰、加密和解密

生成密鑰：

隨機(jī)挑選兩個(gè)不同的素?cái)?shù) $p$ 和 $q$
計(jì)算 $n=p*q$
計(jì)算n的卡邁克爾函數(shù)值 $\lambda(n)$ ，也就是 $p-1$ 和 $q-1$ 的最小公倍數(shù)（least common multiple）
在 $1$ 和 $\lambda(n)$ 之間選取一個(gè)和 $\lambda(n)$ 互質(zhì)的整數(shù) $e$ （也就是和 $\lambda(n)$ 的最大公倍數(shù)是1的整數(shù)）
計(jì)算 $e\ mod\ \lambda(n)$ 的一個(gè)模逆元 $d$ ，用人話說就是找到 $d$ 使得 $(d*e)\%(\lambda(n)) = 1$

公鑰由模數(shù) $n$ 和指數(shù) $e$ 組成，私鑰由模數(shù) $n$ 和指數(shù) $d$ 組成。 $p$$q$ 和 $\lambda(n)$ 都必須保密，因?yàn)樗麄兡苡脕碛?jì)算 $d$ 。

使用密鑰：

如果B想發(fā)送消息給A，B會(huì)首先用A的公鑰去加密信息，然后把加密的信息傳遞給A，最后A用自己的密鑰去解密密文。對(duì)于第三方，如果沒有A的密鑰就無法解密B的密文，所以這個(gè)信息只有A能夠看到。

加密過程：

如果B想發(fā)送信息 $M$ 給A，首先獲得A的公鑰 $n$ 和 $e$ ，加密的密文就是

$c=m^e\ mod\ n$

解密過程：

A收到B的信息 $c$ 之后，用自己的密鑰 $n$ 和 $d$ 解密

$c^d\ mod\ n=(m^e\ mod\ n)^d\ mod\ n= m$

舉個(gè)例子：

生成密鑰首先選取兩個(gè)質(zhì)數(shù): $p=61$ ， $q=53$
計(jì)算 $n=61\times53=3233$
計(jì)算 $\lambda(n)=lcm(60,52) = 780$
選取 $e=17$
找到模逆元 $d=413$ ，因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=413%5Ctimes17%3D7021%E2%80%AC" alt="413\times17=7021" mathimg="1">， $7021\%780=1$
假設(shè)信息為 $m=65$ ，加密的密文為 $c=65^{17}\ mod\ 3233=2790$
收到信息后進(jìn)行解密，解密信息為 $m=2790^{413}\ mod\ 3233=65$

為什么說這個(gè)加密算法很難破解呢？因?yàn)樵趯?shí)踐中很容易找到符合要求的一組特別大的 $e$ 、 $d$ 和 $n$ 使得所有的小于 $n$ 的整數(shù) $m$ 都能滿足

$(m^d)^e\ mod\ n =\ m$

但是如果我們僅僅知道 $e$ 和 $n$ ，憑借現(xiàn)在計(jì)算機(jī)能夠提供的算力卻幾乎不能計(jì)算出 $d$ （對(duì)于特別大的素?cái)?shù)的因式分解是一件特別困難的事情），而沒有 $d$ 就不能解密信息。所以選取的素?cái)?shù)的越大，破解的難度就越大，加密算法就越安全。

總結(jié)

這篇文章寫著寫著就扯遠(yuǎn)了，從leetcode題目到RSA加密算法。素?cái)?shù)個(gè)數(shù)的計(jì)算用到了埃拉托色尼篩選法，時(shí)間復(fù)雜度為 $O(nloglogn)$ ，空間復(fù)雜度為 $O(n)$ ，這篇文章給出了詳細(xì)的時(shí)間復(fù)雜度的證明，為了節(jié)省篇幅忽略了基礎(chǔ)定理的證明。在哈希算法中我們使用素?cái)?shù)來盡量減少鍵的沖突，提高效率。在RSA加密算法中，創(chuàng)作者利用了兩個(gè)大素?cái)?shù)乘積很難進(jìn)行因式分解的特點(diǎn)以及費(fèi)馬小定律設(shè)計(jì)了一套加密和解密信息的規(guī)則，使RSA成為當(dāng)今應(yīng)用最多的非對(duì)稱加密加密協(xié)議。

參考

Prime Numbers–Why are They So Exciting?
prime number
What is a Prime Number?
如何高效判定、篩選素?cái)?shù)
LeetCode一求素?cái)?shù)算法優(yōu)化的簡單研究
 How is the time complexity of Sieve of Eratosthenes is n*log(log(n))?
調(diào)和級(jí)數(shù)近似求和公式推導(dǎo)
歐拉乘積公式的推導(dǎo)過程
 泰勒公式
 泰勒級(jí)數(shù)
Prime Numbers in Hash Functions
RSA (cryptosystem)
Why RSA Works: Three Fundamental Questions Answered
EULER AND THE PARTIAL SUMS OF THE PRIME HARMONIC SERIES
Mertens' theorems

更多內(nèi)容請(qǐng)看我的個(gè)人博客

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

leetcode實(shí)戰(zhàn)—素?cái)?shù)（埃拉托色尼篩選法包括證明、哈希、RSA）

leetcode實(shí)戰(zhàn)—素?cái)?shù)（埃拉托色尼篩選法包括證明、哈希、RSA）

前言