本文共 997 字，大约阅读时间需要 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 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！