[算法] 欧拉线性筛法

介绍

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <cstring>
using namespace std;
int prime[1100000], primesize, phi[11000000];
bool isprime[11000000];
void getlist(int listsize)
{
memset(isprime, 1, sizeof(isprime));
isprime[1] = false;
for (int i = 2; i <= listsize; i++)
{
if (isprime[i])
prime[++primesize] = i;
for (int j = 1; j <= primesize && i * prime[j] <= listsize; j++)
{
isprime[i * prime[j]] = false;
if (i % prime[j] == 0)
break;
}
}
}

  以上就是线性晒代码,他与埃氏筛法不同:

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

  这句代码保证了每个数最多被筛一次,将时间复杂度降到了线性。

证明如下:
prime[]数组中的素数是递增的,当i能整除prime[j],那么i * prime[j+1]这个合数肯定被prime[j]乘以某个数筛掉。
因为i中含有prime[j] , prime[j]prime[j+1] 小,即i = k * prime[j],那么i * prime[j+1] = (k * prime[j]) * prime[j+1] = k’ * prime[j];
接下去的素数同理。所以不用筛下去了。
因此,在满足i % prime[j] == 0这个条件之前以及第一次满足改条件时,prime[j]必定是prime[j] * i的最小因子。

  大名鼎鼎的线性晒日常筛素数的速度大概是埃氏筛的3-4倍,然而在小数据中却有被完爆的可能QAQ

  所以欧拉筛法不只是拿来筛个素数,更重要的一点是线性筛可以用来求解积性函数。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#define SIZE 100

using namespace std;

int main()
{
int check[SIZE] = {0}; //元素值为0代表是素数
int prime[SIZE] = {0}; //存放素数的数组
int pos = 0; //当前素数存在的数量
for (int i = 2; i < SIZE; i++)
{
if (!check[i]) //如果是素数
prime[pos++] = i; //将素数放进其中

for (int j = 0; j < pos && i * prime[j] < SIZE; j++) //判断当前的素数的倍数是不是已经超过了限制的范围
{
check[i * prime[j]] = 1; //筛掉当前素数的倍数
//标注一👇关键
if (i % prime[j] == 0) //如果当前的数能够整除钱前面的素数的话,更换下一个;
break;
}
}
int k = 0;
while (prime[k] != 0)
{
k++;
cout << prime[k] << " ";
}
cout << endl;
system("pause");
return 0;
}