一、定義

質(zhì)數(shù)(prime number)又稱素數(shù)，有無限個。一個大于1的自然數(shù)，除了1和它本身外，不能被其他自然數(shù)整除，換句話說就是該數(shù)除了1和它本身以外不再有其他的因數(shù);否則稱為合數(shù)。

二、相關(guān)定理

• 在一個大于1的數(shù)a和它2倍之間（即區(qū)間(a, 2a]中）必存在至少一個素數(shù)。
• 存在任意長度的素數(shù)等差數(shù)列。（格林和陶哲軒，2004年）
• 一個偶數(shù)可以寫成兩個數(shù)字之和，其中每一個數(shù)字都最多只有9個質(zhì)因數(shù)。（挪威布朗，1920年）
• 一個偶數(shù)必定可以寫成一個質(zhì)數(shù)加上一個合成數(shù)，其中的因子個數(shù)有上界。（瑞尼，1948年）
• 一個偶數(shù)必定可以寫成一個質(zhì)數(shù)加上一個最多由5個因子所組成的合成數(shù)。后來，有人簡稱這結(jié)果為 (1 + 5) (中國，1968年)
• 一個充分大偶數(shù)必定可以寫成一個素數(shù)加上一個最多由2個質(zhì)因子所組成的合成數(shù)。簡稱為 (1 + 2) (中國陳景潤)

三、著名猜想

哥德巴赫猜想：是否每個大于2的偶數(shù)都可寫成兩個素數(shù)之和？

孿生素數(shù)猜想：孿生素數(shù)就是差為2的素數(shù)對，例如11和13。是否存在無窮多的孿生素數(shù)？

斐波那契數(shù)列內(nèi)是否存在無窮多的素數(shù)？是否有無窮多個的梅森素數(shù)？在n2與（n+1）2之間是否每隔n就有一個素數(shù)？是否存在無窮個形式如X2+1素數(shù)？

四、性質(zhì)

（1）質(zhì)數(shù)p的約數(shù)只有兩個：1和p。

（2）初等數(shù)學基本定理：任一大于1的自然數(shù)，要么本身是質(zhì)數(shù)，要么可以分解為幾個質(zhì)數(shù)之積，且這種分解是唯一的。

（3）質(zhì)數(shù)的個數(shù)是無限的。

（4）質(zhì)數(shù)的個數(shù)公式π（n）是不減函數(shù)。

（5）若n為正整數(shù)，在n的2次方到（n+1）的2次方?之間至少有一個質(zhì)數(shù)。

（6）若n為大于或等于2的正整數(shù)，在n到n!之間至少有一個質(zhì)數(shù)。

（7）若質(zhì)數(shù)p為不超過n(n大于等于4)的最大質(zhì)數(shù)，則p>n/2?。

五、著名難題

哥德巴赫猜想

黎曼猜想

孿生質(zhì)數(shù)

梅森質(zhì)數(shù)

六、求質(zhì)數(shù)的方法

1、一般

從2到n-1判斷有沒有能整除n的數(shù)。如果有，則不是素數(shù)，否則，是素數(shù)

bool is_prime(int n){if (n < 2){return false;}int i;for (i = 2; i < n; i++){if (n%i == 0){return false;}}return true; }

2、優(yōu)化

從2一直算到sqrt(n)，這樣算法復雜度降低了很多

bool is_prime(int n){if (n < 2){return false;}int i;for (i = 2; i*i <= n; i++){if (n%i == 0){return false;}}return true; }

3、米勒拉賓素數(shù)測試

int tab[]={2, 3, 5, 7}; long long qpow(int a, int b, int r) //(a^b)%r 快速冪取模 {long long ret = 1, tmp = a;while(b){if (b&1)ret = ret*tmp%r;tmp = tmp*tmp%r;b >>= 1;}return ret; } bool Miller_Rabbin(int n, int a)//米勒拉賓素數(shù)測試 {int r = 0, s = n-1, j;long long k;if(n%a == 0) return false;while((s&1) == 0){s >>= 1;r++;}k = qpow(a, s, n);if(k == 1) return true;for (j = 0; j < r; j++, k=k*k%n)if (k == n-1)return true;return false; } bool Isprime(int n)//判斷是否是素數(shù) {for (int i = 0; i < 4; i++){if (n == tab[i])return true;if (!Miller_Rabbin(n, tab[i]))return false;}return true; }

4、普通篩

時間復雜度是O(nloglogn)，不足之處在于一個合數(shù)可能被篩選多次。

void Prime(){memset(tag,0,sizeof(tag));tag[0]=tag[1]=1;int cnt=0;for(int i=2; i*i <= n; i++)if(tag[i]==0){prime[cnt++]=i;for(int j=i+i;j<=n;j+=i)tag[j]=1;} }

5、線性篩

時間復雜度為O(n)，原因在于每個合數(shù)保證只被它最小的那個質(zhì)因子篩選。關(guān)鍵代碼在第10，11行，因為如果i能整出prime[j]，那么i肯定是個合數(shù)，且i中有質(zhì)因子肯定小于等于prime[j]，所以到此就可以停止了，因為后面的prime[]會比i小的那個質(zhì)因子要大。

void Prime(){memset(tag,0,sizeof(tag));int cnt=0;tag[0]=tag[1]=1;for(int i = 2; i<N; i++){if(!tag[i])prime[cnt++]=i;for(int j=0;j<cnt && prime[j]*i<N; j++){tag[i*prime[j]] = 1;if(i % prime[j]==0)break;}} }

總結(jié)

以上是生活随笔為你收集整理的质数(Prime_Number)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。