埃氏篩法

如果只對一個整數進行素性測試,通常O(√n)算法就足夠了。但如果要對許多整數進行素性測
試,則有更為高效的算法。

要枚舉n以內的素數，就可以用埃氏篩法。這是一個與輾轉相處法一樣古老的算法。

首先,將2到n范圍內的所有整數寫下來。其中最小的數字2是素數。將表中所有2的倍數都劃去。表中剩余的最小數字是3,它不能被更小的數整除,所以是素數。再將表中所有3的倍數都劃去。依此類推,==如果表中剩余的最小數字是m時,m就是素數。然后將表中所有m的倍數都劃去。==像這樣反復操作,就能依次枚舉n以內的素數。

以下為代碼

#include<iostream> #define maxn 9999999 using namespace std; int prime[maxn];//第i個素數 bool is_prime[maxn];//is_prime【i】是true表示i是素數 int solve(int n) {int res = 0;for (int i = 0; i <= n; i++)is_prime[i] = true;//初始化is_prime[0] = is_prime[1] = false;//0和1排除for (int i = 2; i <= n; i++){if (is_prime[i]){prime[res++] = i;for (int j = 2 * i; j <= n; j += i)//除去i的倍數is_prime[j] = false;}}return res; }int main() {int n;while (cin >> n){int res;res = solve(n);cout << res << endl;}return 0; }

總結

以上是生活随笔為你收集整理的埃氏筛法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。