素数筛法
发布日期:2021-09-23 21:27:26 浏览次数:0 分类:技术文章

本文共 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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:Vijos 1304题:回文数
下一篇:两个变量交换值的方法

发表评论

最新留言

表示我来过!
[***.172.111.71]2022年05月22日 10时16分09秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

最新文章