美文网首页
生成素数表算法(埃拉托斯特尼筛法)

生成素数表算法(埃拉托斯特尼筛法)

作者: yz_wang | 来源:发表于2018-01-31 17:04 被阅读0次

ref:wikipedia




动态解释图
bool mark[100001];  //有没有遍历过
int prime[100001];  
int primeSize; 

void init()
{  
  primeSize = 0;  
  for (int i = 2; i <= 100000; i++)   //质数因子
   {  
     if (mark[i] == true)continue;  
     prime[primeSize++] = i;  
     if (i >= 1000)continue;          //终止条件
     for (int j = i * i; j <= 100000; j += i)
         {  
            mark[j] = true;  
         }  
    }  
}  

相关文章

网友评论

      本文标题:生成素数表算法(埃拉托斯特尼筛法)

      本文链接:https://www.haomeiwen.com/subject/wollzxtx.html