您好,登錄后才能下訂單哦!
什么是求素?cái)?shù)
素?cái)?shù)指的是因子只有1和本身的數(shù)(1不是素?cái)?shù)),求解素?cái)?shù)在數(shù)學(xué)上應(yīng)用非常廣泛,而求解n以內(nèi)的素?cái)?shù)也是我們編程時(shí)常遇到的問題,在這個(gè)問題上,篩選法求解素?cái)?shù)運(yùn)行得非???。
i在2到n-1之間任取一個(gè)數(shù),如果n能被整除則不是素?cái)?shù),否則就是素?cái)?shù)
稱篩法
篩選法又稱篩法,是求不超過自然數(shù)N(N>1)的所有質(zhì)數(shù)的一種方法。據(jù)說是古希臘的埃拉托斯特尼(Eratosthenes,約公元前274~194年)發(fā)明的,又稱埃拉托斯特尼篩子。
具體做法是:
先把N個(gè)自然數(shù)按次序排列起來。1不是質(zhì)數(shù),也不是合數(shù),要?jiǎng)澣ァ5诙€(gè)數(shù)2是質(zhì)數(shù)留下來,而把2后面所有能被2整除的數(shù)都劃去。2后面第一個(gè)沒劃去的數(shù)是3,把3留下,再把3后面所有能被3整除的數(shù)都劃去。3后面第一個(gè)沒劃去的數(shù)是5,把5留下,再把5后面所有能被5整除的數(shù)都劃去。這樣一直做下去,就會(huì)把不超過N的全部合數(shù)都篩掉,留下的就是不超過N的全部質(zhì)數(shù)。因?yàn)橄ED人是把數(shù)寫在涂臘的板上,每要?jiǎng)澣ヒ粋€(gè)數(shù),就在上面記以小點(diǎn),尋求質(zhì)數(shù)的工作完畢后,這許多小點(diǎn)就像一個(gè)篩子,所以就把埃拉托斯特尼的方法叫做“埃拉托斯特尼篩”,簡稱“篩法”。(另一種解釋是當(dāng)時(shí)的數(shù)寫在紙草上,每要?jiǎng)澣ヒ粋€(gè)數(shù),就把這個(gè)數(shù)挖去,尋求質(zhì)數(shù)的工作完畢后,這許多小洞就像一個(gè)篩子。)
普通枚舉法:
#include <iostream> #include <string> #include <cmath> #include <cstring> using namespace std; bool isPlain(int x){ if(x<2) return false; else{ for(int i=2;i<x;i++) { if(!(x%i)) return false; } } return true; } int main() { int n; cin>>n; int cot=0; for(int j=0;j<n;j++){ if(isPlain(j)){ cout<<j<<((++cot%7==0)?"\n":"\t"); } } }
篩選法:
原始版本:
#include <iostream> #include <string> #include <cmath> #include <cstring> using namespace std; int main() { int n; cin>>n; bool* ans=new bool[n]; memset(ans,true,sizeof(bool)*n);// ans[0]=false; ans[1]=false; for(int i=2;i<n;i++){ if(ans[i]){ for(int j=i*2;j<n;j+=i){//倍數(shù)取整 ans[j]=false; } } } int col = 0; for(int i=0;i<n;i++){ if(ans[i]){ cout<<i<<" "; } } return 0; }
改進(jìn)版本
#include <iostream> #include <string> #include <cmath> #include <cstring> #include <bitset> using namespace std; int main() { int n; cin>>n; bitset<100000> ans; ans.set(0); ans.set(1); for(int j=2; j<=sqrt(n); j++) { for(int i=2*j; i < n; i+=j) { ans.set(i); } } int cot=0; for(int i=0; i<n; i++) { if(ans[i]!=1) { cout<<i<<((++cot%7==0)?"\n":"\t"); } } }
總結(jié)
以上就是這篇文章的全部內(nèi)容了,希望本文的內(nèi)容對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,如果有疑問大家可以留言交流,謝謝大家對億速云的支持。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。