博主简单的写下这篇文章，主要为了更好地复习和理解，希望对各位有帮助。

素数：指一个只能被1和它本身整除的数。

青铜级别求素数：枚举范围内的每个数在2到本身的范围中是否有被整除的数。没有就是素数，有就不是素数。

int IsPrime(int n){

int i;

if(n <= 1) return 0;

if(n==2) return 1;

for(i = 2;i < n;i++) if(n%i==0) return 0;

return 1;

}

白银级别求素数：此法与第一种差不多，唯一变化就是枚举是否有被整除的数的范围。由于2*4=8与4*2=8是一样的，减少重复，提高程序效率。

int IsPrime(int n){

int i;

if(n <= 1) return 0;

if(n==2) return 1;

for(i=2;i<=n/2;i++) if(n%i==0) return 0;

return 1;

}

黄金级别求素数：由于所有素数（除了2）都是从奇数中出现。所以我们可以先去掉偶数，再筛选，这样的效率就会更高一点

int IsPrime(int n){

int i;

if(n==2) return 1;

if(n<=1||n%2==0) return 0;

for(i=3;i<=n/2;i+=2)if(n%i==0) return 0;

return 1;

}

铂金级别求素数：求素数方法同上一种，在范围内找素数，去掉此范围中的偶数。如for(int i=3;i<=1000;i+=2),找1000以内的素数

钻石级别求素数：

int IsPrime(int n){

int i;

if(n%2==0) return 0;

for(i = 3;i <= sqrt(n);i+=2) if(n%i==0) return 0;

return 1;

}

星耀级别求素数：标记范围内所有数，然后判断

1）去掉2的倍数；2）去掉3的倍数；3）去掉4的倍数(不需要，第一步已经去掉了)....直到不能去掉为止。

void IsPrime(int n){

int i,j;

for(i=2;i<=n;i++) prime[i]=1;

for(i=2;i<=n;i++){

if(prime[i]) printf(" %d ",i);

for(j=i+i;j<=n;j+=i) prime[j] = 0;

}

}

王者求素数：

1）定义一个数组a去存储素数。然后不断去标记范围内不是素数的数（也就是素数的倍数a[j]*i）。

2）i%a[j]==0，使任一个合数，只能被它的最小质因数（18=2*3*3，最小质因数为2）标记一次。因为一遇到最小质因数a[j]就跳出。

void IsPrime(int n){

int i,j,len=0;

for(i=0;i

for(i=2;i<=n;i++){

if(prime[i]) {

a[len++]=i;

printf("%d ",i);

}

for(j=0;j

prime[a[j]*i]=0;

if(i%a[j]==0) break;

}

}

}

以上就是求素数的几种方法，一般来说，我们都是选最后两种方法。