素数筛

START:

暴力

从 1 - n

想法

按照素数的定义来嘛，除了 1 和它本身没有别的因子，就是素数

代码

for(int i = 2; i < n; i++)
{
    if(n % i ==0) 
    {
        break;
    }

}
if(i == n) 
{
    is_prime = true;
}
else
{
    is_prime = false;
}

特点

辣鸡算法，n 稍微大一点就慢慢等吧。

从 1 - sqrt(n)

想法

因子都是成对出现的，并且均匀地分布在 sqrt(n) 周围，所以只需要比一半。

代码

for(int i = 2; i < sqrt(n); i++)
{
    if(n % i ==0) 
    {
        break;
    }
}
if(i >= sqrt(n)) 
{
    is_prime = true;
}
else
{
    is_prime = false;
}

特点

还是辣鸡，容易爆。

普通筛

埃氏筛

想法

素数的倍数一定不是素数。

实现

用一个 n+1 长度的bool数组is_prime保存，从第一个素数 2开始，置其倍数为true 一直到大于 n 然后继续下一趟。

代码

int is_prime[n] = {0};
bool vis[n] = {false};
int total = 0;//素数的个数
for(int i= 2; i < n; i++)
{
    if(!vis[n])
    {
        prime[total] = i;
        total++;
    }
    
	for(int j = 2i; j < n; j +=i)
    {
        vis[j] = true;
    }
}

特点

时间复杂度O(nloglogn)空间复杂度 O(n)

标记过一边的东西又被标记一边，感觉好蠢，为啥不能直接把第二个for j放到if 里去？

验证发现可以，但是用时差不多。

线性筛

想法

每个合数只会被它的最小质因子筛去，因此每个数只会被标记一次，所以复杂度为O(n)。

代码

int is_prime[maxn] = { 0 };
bool vis[maxn] = { false };
int total = 0;
for(int i = 2; i < maxn; i++)
{
    if(!vis[i])
    {
        is_prime[total] = i;
        total++;
    }
    
    for(int j = 0; j< total; j++)
    {
        if(i * is_prime[j] > maxn)//	如果越界
        {
            break;
        }
        
        vis[i * is_prime[j]] = 1;//	如果 i 是合数，i 一直到能把 i 整除的倍数都会									  	被标记
        
        if(i % is_prime[j] == 0)//	保证只会被最小质因子标记
        {
            break;
        }
    }
}

证明

先决条件：

• 任何合数等于一系列素数的积，即一个特定的素数序列可以决定任意一个合数，这种关系可以被定义为一种映射。

不论 i是否是素数，都会执行到第 12 行的 for循环：

1. 如果 i是素数，两个素数所组成的素数序列一定是特异的，我们将这个序列叫做p。

2. 如果 i是合数，就可以把它看成一组素数序列，并在其末尾增加一个p[j],虽然这个序列的顺序并不影响映射关系，但为了方便研究，使其有序，并令p这个序列是一个递增的序列。

   因此可以知道，p[0]是序列p中的最小值。

   根据第 21 行，当is_prime[j]能够被i整除的时候，且is_prime序列是递增排列的，我们可以得到一个结果：

   此时is_prime[j]即为序列p中的p[0]。

   那么就可以说明，第 21 行代码只能筛出不大于p[0]的素数。

证明举例

假设序列p的元素有p0 = {2,3,5}，这个序列可以筛出2*i而不能筛出3*i。

如果能够筛出3*i，那么当p1 = {3,3,5}时，必定会重复标记。

参考

1. 线性筛求素数-Grubbyskyer 暴力部分，普通筛中埃氏筛全部，线性筛除证明和证明举例部分。

2. 一般筛法求素数+快速线性筛法求素数-dinosoft 线性筛中证明和证明举例部分。

END