素?cái)?shù)

@(算法)

素?cái)?shù)簡(jiǎn)介

質(zhì)數(shù)（prime number）又稱(chēng)素?cái)?shù)。
質(zhì)數(shù)定義為在大于1的自然數(shù)中，除了1和它本身以外不再有其他因數(shù)。還能被其他數(shù)（0除外）整除的數(shù)為合數(shù)。

判斷一個(gè)數(shù)是否是素?cái)?shù)
根據(jù)定義，除了1和本身之外沒(méi)有其他約束，
所以判斷是否為質(zhì)數(shù)，
根據(jù)定義直接判斷從2到n-1是否存在n的約數(shù)。

方法一：暴力破解！

bool isPrime(int num){for(int i=2;i<num;i++){if(num%i ==0){return 0;}}return 1; }

上述方法，明顯存在效率極低的問(wèn)題。
一個(gè)數(shù)若可以進(jìn)行因式分解，那么分解時(shí)得到的兩個(gè)數(shù)，一定
是一個(gè)小于等于sqrt(n)，一個(gè)大于等于sqrt(n)

改進(jìn)：

bool isPrime(int num){int t=sqrt(num);for(int i=2;i<num;i++){if(num%i ==0){return 0;}}return 1; }

方法二：素?cái)?shù)篩法

可以提前處理出來(lái)1~n 的全體素?cái)?shù) 1.把1~n列出來(lái) 2.去掉不是特殊的1 3.從小到大，枚舉每一個(gè)沒(méi)有刪掉的數(shù)字i把 i 的2倍，3倍，4倍，...,刪掉剩下的沒(méi)被刪掉的都是素?cái)?shù) const int N=100; int notprime[N]; int main(){notprime[1]=1;for(int i=2;i<N;i++){if(notprime[i]==0){for(int j=i+i;j<N;j=j+i){ 刪掉2*i,3*i,4*i......notprime[j]=1;}}}for(int i=1;i<N;i++){if(notprime[i]!=1){printf("%d\t",i);}}return 0; }

方法三：歐拉篩法

在素?cái)?shù)篩法中，有很多合數(shù)被刪除多次。而歐拉篩法提供兩個(gè)數(shù)組，一個(gè)是素?cái)?shù)表，另一個(gè)是刪除合數(shù)表(值為1表示表示不是素?cái)?shù))。 const int N=100; int notprime[N]; //刪除標(biāo)記,值為1表示表示不是素?cái)?shù) int prime[N]; //素?cái)?shù)表 int main(){int t=0; //初始化素?cái)?shù)表為空notprime[1]=1;for(int i=2;i<N;i++){if(notprime[i]==0){ //找到一個(gè)沒(méi)有被刪除的數(shù)prime[t++]=i; //加入素?cái)?shù)表}for(int j=0;j<t&&prime[j]*i<N;j++){ //枚舉素?cái)?shù)表notprime[prime[j]*i]=1;if(i%prime[j]==0){break; //保證了每個(gè)合數(shù)只會(huì)被它的最小素因子篩掉}}}for(int i=0;i<N;i++){if(prime[i]!=0){printf("%d\t",prime[i]);}} } prime[]數(shù)組中的素?cái)?shù)是遞增的,當(dāng)i能整除prime[j]，那么 prime[j]*i 這個(gè)合數(shù)肯定被prime[j]乘以某個(gè)數(shù)篩掉。i%prime[j]==0保證了每個(gè)合數(shù)只會(huì)被它的最小素因子篩掉。

參考
[1]http://www.cnblogs.com/zhuoha...
[2]http://www.cnblogs.com/zhuoha...
[3]https://baike.baidu.com/item/...

總結(jié)

以上是生活随笔為你收集整理的关于素数的那些事儿的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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