本文共 1066 字，大约阅读时间需要 3 分钟。

要判断一个数是不是素数，最简单也是绝大多数教科书中用的方法如下：

bool isPrime(int n){
       if(n == 2) return true;    if(n < 2 || n % 2 == 0) return false;    for(int i = 3; i <= sqrt(n); i += 2)        if(n%i == 0) return false;    return true;}

但当要判断的区间很大时，上面的方法就显得很不实用，几乎所有有关ACM的求素数的题目几乎都不能用上面的方法求解，而要用到下面的素数筛法：

void isPrime(){
       prime[0] = prime [1] = 0, prime[2] = 1;    for(int i = 3; i <= MAX; i++)	    prime[i] = i % 2 == 0 ? 0 : 1;    for(int i = 3; i <= sqrt(MAX); i++)       if(prime[i])	       for(int j = i * i; j < n; j += 2 * i)	           prime[j] = 0;}

最后附上求到一个数之间的所有素数的程序代码：

#include 
   
    #include 
    
     #define MAX 10000int prime[MAX];void isPrime()    {
           prime[0] = prime [1] = 0, prime[2] = 1;        for(int i = 3; i <= MAX; i++)            prime[i] = i % 2 == 0 ? 0 : 1;        for(int i = 3; i <= sqrt(MAX); i++)           if(prime[i])               for(int j = i * i; j < MAX; j += 2 * i)                   prime[j] = 0;    }int main(){
       isPrime();    for(int i = 2; i < MAX; i++)    {
           if(prime[i])            printf("%d\n", i);    }}
    
   

转载地址：https://blog.csdn.net/bodhiye/article/details/54412475 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！