筛质数

概念

质数（素数）是指在大于1的自然数中，除了1和它本身之外没有其他正因数（除了1和本身以外没有其他能够整除它的正整数）。换句话说，一个质数只能被1和自身整除，不能被其他任何正整数整除。

试除法求质数

试除法是一种简单而直观的方法，用于确定一个数是否是质数。该方法的基本思想是通过逐一尝试除以小于该数平方根的所有可能因数，来检查是否存在除了1和该数本身之外的其他因数。如果找到了一个能够整除的因数，那么这个数就不是质数；否则，它就是质数。

时间复杂度$O(\sqrt n)$

bool Is_prime(int n)
{
    if(n<2) return false;
    for(int i=2;i<=n/i;++i)
        if(n%i==0) return false;
    return true;
}

但是有的时候，我们要想知道比如$1 ~ 100000$ 的所有质数，这样就需要循环很多次。所以出现了筛质数，把质数都筛选出来，存储起来。

线性筛法求质数

线性筛法是一种高效的算法，用于筛选出小于等于某个给定数的所有质数。与传统的试除法相比，线性筛法的优势在于它只需遍历一次，而且每个合数只被标记一次。这使得它在处理大范围的质数筛选时效率更高。
时间复杂度$O(n)$

原理

1. 标记法： 初始化一个布尔数组 st，数组长度为 n+1，初始所有元素都标记为合数（false）。

2. 遍历质数： 从2开始，逐一遍历到n。对于每个质数i，如果它还没有被标记为质数（即 st[i] 为 false），则将其加入质数列表，然后标记它的所有倍数为合数。

3. 避免重复标记： 在标记的过程中，每个合数都只会被标记一次。这是线性筛法的优势之一，因为它避免了试除法中的重复标记问题。

4. 筛选结果： 最终，筛选出的质数都存储在 primes 数组中。

   int primes[N],cnt;//存所有质数
   bool st[N];//记录i有没有被筛过
   
   void get_primes(int n)//筛选2~n的素数
   {
   	for(int i=2;i<=n;++i)
   	{
   		if(!st[i]) primes[cnt++] = i;//如果没有被筛过,证明是素数
   		for(int j = 0;primes[j] * i <=n;j++)
   		{
   		/*p[j]一定小于等于i的质因子*/
   			st[primes[j] * i] = true;//用最小质因子筛掉合数
   			if(i%primes[j] == 0) break;
   		}
   	}
   }

存最小质因子

int primes[N],cnt;//存所有质数
bool st[N];//记录i有没有被筛过
//****
int minp[N];//每个数的最小质因子
//****
void get_primes(int n)//筛选2~n的素数
{
	for(int i=2;i<=n;++i)
	{
		if(!st[i]) minp[i]=i,primes[cnt++] = i;//如果没有被筛过,证明是素数
		for(int j = 0;primes[j] * i <=n;j++)
		{
		/*p[j]一定小于等于i的质因子*/
			st[primes[j] * i] = true;//用最小质因子筛掉合数
			minp[primes[j] * i] = primes[j];
			if(i%primes[j] == 0) break;
		}
	}
}