素数是指除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("%4d ",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 100void 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("%4d ",i);}int main(){    prime(10000);    getchar();}

埃拉托色尼（Eratosthenes，公元前275一前193）生于希腊在非洲北部的殖民地昔兰尼（cyrene，在今利比亚）。他在昔兰尼和雅典接受了良好的教育，成为了一位博学的哲学家、诗人、天文学家和地理学家。他的兴趣是多方面的，不过他的成就则主要表现在地理学和天文学方面。

－End－