线性素数筛(欧拉筛)

思路：

给定n，求1~n间的素数，一般有以下几种方法

1.傻瓜解法：n,n/2

int prime[N] = { 0 };

void fetch_prime(ll n)
{
  int step = 0;
  for(int i = 2; i < n; i++)
  {
    for (int j = 2; j < i/ 2; j++)
    {
      if (i % j == 0)
        break;
    }
    if (i == n)
      prime[step++] = i;
  }
}

只比用纸笔算的来的快

 

2.一般解法：√n

int prime[N] = { 0 };

void fetch_prime(ll n)
{
  ll i = 2, j, step = 0;
  for (int i = 2; i < n; i++)
  {
    for (int j = 2; j* j < i; j++)
    {
      if (i % j == 0)
        break;
    }
    if (i == n)
      prime[step++] = i;
  }
}

稍微快一些

3.普通筛法：素数的倍数一定不是素数

4.线性筛法：不重复筛去

//线性素数筛
const int maxn = 65535;
int prime[maxn] = { 0 }, isNotPrime[maxn] = { 1, 1 }, primeCnt = 0;

void soe()
{
	for (int i = 2; i < maxn; i++)
	{
		if (!isNotPrime[i])
		{
			prime[primeCnt++] = i;
		}
		for (int j = 0; j < primeCnt && i * prime[j] < maxn; j++)
		{
			isNotPrime[i * prime[j]] = 1;
			if (!(i % prime[j]))
			{
				break;
			}
		}
	}
}

证明：

1、没有重复筛

一个合数可以被分解成p[1]*p[2]*…p[n]，并且保证p[1]<p[2]<…<p[n]。例如，在n=3时，筛掉这个合数的机会有：p[1]和p[2]*p[3]，p[2]和p[1]*p[3]，p[3]和p[1]*p[2]，而我们选择的那个质数必须小于那个合数的最小质因子，如p[2]和p[1]*p[3]，因为p[2]>p[1],所以这样是筛不到的。唯一会筛的是第一种：p[1]和p[2]*p[3]。

2、没有漏筛

还是假设把这个合数分解质因数p[1]*p[2]*…p[n]，保证p[1]<p[2]<…<p[n]，在n=3时，我们设s=p[2]*p[3]，s肯定小于刚才那个合数，说明肯定对于它已经筛过，然后p[1]肯定小于s，因为s=p[2]*p[3]，即p[1]是最小的因子。说明p[1]*s也就是这个合数一定筛过。

证明看不明白就背代码吧。。。