求素數是比較基本的內容，有時候我們會需要打一個素數表。一般如果n比較小我們會使用（%2~sqrtn）這種算法，簡單但是時間耗費很多，復雜度是O(n^2)。這里介紹一種篩選求素數法，基本要點是，如果找到一個素數如3，那么就往后篩出所有3的倍數。

一般篩選求素數：

void init() {memset(prim, true, sizeof(prim));for (int i = 2; i*i <= maxn; i++){if (prim[i]) //如果是素數就把其倍數全刪掉for (int j = i; i*j <= maxn; j++)//j從i開始可以避免一部分重復prim[i*j] = false;} }這個方法比一般的打表法快，但運算中間有大量重復，如：i=2時，篩除30=2*15，但i=5時，篩除30=5*6，重復的標示了。 void init() {for (int i = 2; i < maxn; i++){if (!map[i]){for (int j = i; j < maxn; j+=i)map[j] = map[j / i] + 1; //這樣還可以統計i由幾個素因子構成}} }

線性篩選求素數：

void init() {memset(notprim, false, sizeof(notprim));int cnt = 0;for (int i = 2; i <= maxn; i++){if (!notprim[i]) prim[cnt++] = i; //如果是素數直接賦值for (int j = 0; j < cnt&&i*prim[j] <= maxn; j++)//如果是合數，將前面所有的素數乘當前i篩去{notprim[i*prim[j]] = true;if (i%prim[j] == 0) //關鍵處:如果當前合數中出現前面已經出現的素數就跳出break;}} } 首先要明確，所有合數都可以由素數相乘得到。 所以如果 i 是合數，此時 i 可以表示成遞增素數相乘 i=p1*p2*...*pn, pi都是素數（2<=i<=n）， pi<=pj ( i<=j )，p1是最小的系數。
根據“關鍵處”的定義，當p1==prim[j] 的時候，篩除就終止了，也就是說，只能篩出不大于p1的質數*i。 我們可以直觀地舉個例子。i=2*3*5，此時能篩除 2*i ,不能篩除 3*i，如果能篩除3*i 的話，當 i' 等于 i'=3*3*5 時，篩除2*i' 就和前面重復了。

例子：POJ2909 題目要求輸入一個數，輸出有幾種方案，使這個數能等于兩個素數相加

15362476

Seasonal

2909

Accepted

212K

0MS

C++

646B

2016-04-07 08:09:05

#include<stdio.h> #include<stdlib.h> #include<string.h> #define maxn 2<<14 bool notprim[maxn]; int prim[maxn];void init() {memset(notprim, false, sizeof(notprim));int cnt = 0;for (int i = 2; i <= maxn; i++){if (!notprim[i]) prim[cnt++] = i; //如果是素數直接賦值for (int j = 0; j < cnt&&i*prim[j] <= maxn; j++)//如果是合數，將前面所有的素數乘當前i篩去{notprim[i*prim[j]] = true;if (i%prim[j] == 0) //關鍵處:如果當前合數中出現前面已經出現的素數就跳出break;}} }int main() {int n;init();while (scanf("%d", &n), n){int num = 0;for (int i = 2; i * 2 <= n; i++)if (!notprim[i] && !notprim[n - i])num++;printf("%d\n", num);}return 0; }

轉載于:https://www.cnblogs.com/seasonal/p/10343791.html

總結

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

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