文章目錄

• 樸素算法
• • code
• 優(yōu)化
• • code
• 埃氏篩法
• • code

樸素算法

首先，我們得知道素?cái)?shù)的概念：除了1和這個(gè)數(shù)本身，這個(gè)數(shù)沒(méi)有其他因子（約數(shù)），這個(gè)數(shù)就是一個(gè)素?cái)?shù)。不是素?cái)?shù)的數(shù)，就是合數(shù)。

于是，設(shè)這個(gè)數(shù)為n，我們從2枚舉到n-1，只要n模這些數(shù)都不等于0，則n就是素?cái)?shù)。

code

cin>>n; for(int i=2;i<=n-1;i++) {if(n%i==0){flag=1;break;} } if(flag==0) {cout<<n<<"是一個(gè)質(zhì)數(shù)"; } else {cout<<n<<"不是一個(gè)質(zhì)數(shù)"; }

但是這種方法的時(shí)間復(fù)雜度極其大，假設(shè)問(wèn)你從1~n的所有素?cái)?shù)，這種方法就會(huì)爆，于是，我們來(lái)想怎么優(yōu)化。

優(yōu)化

首先，我們得知道一個(gè)定理，一個(gè)數(shù)能被多個(gè)質(zhì)數(shù)給表示出來(lái)，比如說(shuō)24=$2^3?3$，這些因數(shù)就被稱為質(zhì)因數(shù)。

然后，我們還要知道一個(gè)數(shù)最多只有一個(gè)大于sqrt（n）的質(zhì)因數(shù)（sqrt（n）表示的是n的開(kāi)方。），為什么？接下來(lái)就是推導(dǎo)過(guò)程：

我們?cè)O(shè)a和b是n的質(zhì)因數(shù)，且a!=b，a和b同時(shí)大于sqrt（n）。
但是a*b確實(shí)要大于n，而一個(gè)數(shù)的因子相乘不可能大于它本身，所以不可能有兩個(gè)或兩個(gè)以上大于sqrt（n）的質(zhì)因數(shù)。

于是，我們上面的枚舉就不用枚舉到n-1，枚舉到sqrt（n）就可以了。
這時(shí)，有人會(huì)問(wèn)，為什么大于sqrt（n）的那個(gè)質(zhì)數(shù)不用枚舉？
因?yàn)橄胍嬖诖笥趕qrt（n）且小于n的質(zhì)因數(shù)，就必須要有小于sqrt（n）的質(zhì)因數(shù)。

code

cin>>n; for(int i=2;i<=sqrt(n);i++) {if(n%i==0){flag=1;break;} } if(flag==0) {cout<<n<<"是一個(gè)質(zhì)數(shù)"; } else {cout<<n<<"不是一個(gè)質(zhì)數(shù)"; }

埃氏篩法

這個(gè)求素?cái)?shù)的方法在求1~n之間的素?cái)?shù)是比上面的快的。（廢話）

首先，我們知道一個(gè)數(shù)是可以被多個(gè)質(zhì)數(shù)表示出來(lái)的，于是我們就可以在求素?cái)?shù)時(shí)，就把他的倍數(shù)求出來(lái)，然后就可以提前標(biāo)記掉，就可以更快的求出來(lái)了。

在枚舉到一個(gè)素?cái)?shù)的時(shí)候，就枚舉他的倍數(shù)，把他的倍數(shù)標(biāo)記為1，所以標(biāo)記為0的數(shù)就是質(zhì)數(shù)。

code

cin>>n; for(int i=2;i<=n;i++) {if(bz[i]==0){for(int j=i+i;j<=n;j+=i){bz[j]=1;}cout<<i<<"是一個(gè)質(zhì)數(shù)"<<endl;} }

總結(jié)

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

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