素數是指除1以外隻能被1和自身整除的整數。

1 從定義出發的暴力法

#include <stdio.h> bool isPrime(int n) { int ret = 0; for(int i=1;i<=n;i ) // 邊界為[1,n] { if(n%i == 0) ret ; } if(ret == 2) return true; return false; } int main() { for(int i=1;i<100;i ) if(isPrime(i)) printf("%d ",i); getchar(); }

2 暴力結合枚舉和邊界

#include <stdio.h> double sqrt(double x,double y) { if(y*y-x<-1e-5 || y*y-x > 1e-5) return sqrt(x,(y x/y)/2.0); else return y; } bool isPrime(int n) { if(n<2) return false; if(n==2) return true; if(n%2==0) return false; int limit = sqrt(n,n/2) 1; for(int i=3;i<limit;i =2) if(n%i==0) return false; return true; } void prime(int n) { for(int i = 2;i<n 1;i ) if(isPrime(i)) printf("M ",i); } int main() { prime(1000); getchar(); }

3 埃拉托斯特尼素數篩法

素數篩法的思路是：從2開始，不包括2本身，其倍數全部篩掉，剩下的全是素數。

先是篩2的倍數，篩完後剩下的最小整數是3，然後篩3的倍數；

然後篩5的倍數……

demo code:

#include <stdio.h> #include <math.h> #include <string.h> #include <malloc.h> #define N 100 void prime(int n) { int *arr = (int*)malloc(sizeof(int)*(n 1)); memset(arr,0,sizeof(int)*(n 1));// arr[i]==0表示i是素數 arr[1] = 1; int m = sqrt(n) 1; for(int i=2;i<m;i ) if(arr[i]==0) for(int j=i*2; j<=n; j =i) arr[j] = 1; for(i=1;i<=n;i ) if(arr[i]==0) printf("M ",i); } int main() { prime(10000); getchar(); }

埃拉托色尼（Eratosthenes，公元前275一前193）生于希臘在非洲北部的殖民地昔蘭尼（cyrene，在今利比亞）。他在昔蘭尼和雅典接受了良好的教育，成為了一位博學的哲學家、詩人、天文學家和地理學家。他的興趣是多方面的，不過他的成就則主要表現在地理學和天文學方面。

－End－