首页 > 其他 > 详细

线性素数筛

时间:2018-09-22 11:50:13      阅读:194      评论:0      收藏:0      [点我收藏+]
int prime[MAXN], tag[MAXN];
void Get_Prime()
{
    Mem0(tag);
    int cnt = 0;
    for(int i = 2;i < MAXN;++i)
    {
        if(!tag[i])
            prime[cnt++] = i;
        for(int j = 0;j < cnt && i * prime[j] <= MAXN;++j)
        {
            tag[i * prime[j]] = 1;
            if(i % prime[j] == 0)
                break;
        }
    }
}

这个是很多人网上给的图。。。。这里只是搬个图来模拟

还是按上面的例子进行一遍模拟:N=20

 

技术分享图片

下面说一下我的理解(关于网上说的两个重点)

1、

        for(int j = 0;j < cnt && i * prime[j] <= MAXN;++j)

 

对于这个的解释我觉得网上的解释实在看不懂再来看我这个比较好。。。因为我感觉我这个更难懂,但是别人的我看不懂

prime[j] 这里存是小于或等于 i 的所有素数。关于 i * prime[j] ,我们先看一个素数 2,

如果没有下面那个 break 的话

当 i = 3 时,这时候有 2 * 3,

当 i = 4 时,这时候有 2 * 4,(事实上程序跑到这里就 break了)

当 i = 5 时,这时候有 2 * 5。。

类推下去,可以知道,最后算得一定范围内和prime[j] 相关的合数(任何一个数可以用一个或多个素数相乘得到),这个些数是(prime[j] + 1 ~ i) * prime[j]

2、

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

 

网上都说这里保证每个合数只会被它的最小质因数筛去,我就解释一下为什么这里会这样。过程里的主要式子忘了查什么资料哪里瞄到的,当时搭梯子后点来点去的。

质数就不用说了,说合数,每个合数 num 都可以表示成多个质数的积(欧拉函数)

我们设一个合数为 num,这个合数的最小质因数为 a ,那么可得 num = a^k * b;

1、当 k 为 1 时,num = a * b ( a < b)

2、当 k != 1 时,num = a^k * b

这里注意到我们将上面代码的合数表示为 i * prime[j] = num ;当 i % prime[j] == 0 时,那么 prime[j] 为组成 i 的最小的质数(prime 为从小到大排列的质数组),即设 i = c * prime[j] ,那么 num = c * prime[j] * prime[j] = prime[j]^2 * c; 这符合上面的 2,虽然这种推论没有证明充要条件,但是应该能理解吧。。。。

那么上面的 1 呢?不就是 num = i * prime[j] = b * a(prime[j] <= i)

 

线性素数筛

原文:https://www.cnblogs.com/shuizhidao/p/9683542.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!