6567: 学习系列 —— 欧拉筛
[Creator : ]
Description
【知识点】
欧拉筛法的基本思想 ：在埃氏筛法的基础上，让每个合数只被它的最小质因子筛选一次，以达到不重复的目的。欧拉筛法是比埃氏筛法更高效的一种素数筛法，确保每个合数只被筛掉一次，算法复杂度达到 $O(n)$，被称为线性筛。
【时间复杂度】
$O(n)$【代码】
void euler(LL n) {
for (LL i=2;i<=n;i++) {
//cout<<" i = "<<i<<"\n";
if (false==st[i]) {
primes[++cnt]=i;
}
//遍历所有素数，将素数的倍数删除
for (LL j=1;primes[j]<=n/i;j++) {
//cout<<" j = "<<j<<" primes["<<j<<"]"<<" = "<<primes[j]<<" i*primes[j] = "<<i*primes[j]<<"\n";
st[primes[j]*i]=true;
if (i%primes[j]==0) {
break;
}
}
}
}
例如，当 n=100 时候，1 ~ 100 内有 25 个质数，也就是 cnt=25。对应的输出如下：
i = 2
j = 1 primes[1] = 2 i*primes[j] = 4
i = 3
j = 1 primes[1] = 2 i*primes[j] = 6
j = 2 primes[2] = 3 i*primes[j] = 9
i = 4
j = 1 primes[1] = 2 i*primes[j] = 8
i = 5
j = 1 primes[1] = 2 i*primes[j] = 10
j = 2 primes[2] = 3 i*primes[j] = 15
j = 3 primes[3] = 5 i*primes[j] = 25
i = 6
j = 1 primes[1] = 2 i*primes[j] = 12
i = 7
j = 1 primes[1] = 2 i*primes[j] = 14
j = 2 primes[2] = 3 i*primes[j] = 21
j = 3 primes[3] = 5 i*primes[j] = 35
j = 4 primes[4] = 7 i*primes[j] = 49
i = 8
j = 1 primes[1] = 2 i*primes[j] = 16
i = 9
j = 1 primes[1] = 2 i*primes[j] = 18
j = 2 primes[2] = 3 i*primes[j] = 27
i = 10
j = 1 primes[1] = 2 i*primes[j] = 20
i = 11
j = 1 primes[1] = 2 i*primes[j] = 22
j = 2 primes[2] = 3 i*primes[j] = 33
j = 3 primes[3] = 5 i*primes[j] = 55
j = 4 primes[4] = 7 i*primes[j] = 77
i = 12
j = 1 primes[1] = 2 i*primes[j] = 24
i = 13
j = 1 primes[1] = 2 i*primes[j] = 26
j = 2 primes[2] = 3 i*primes[j] = 39
j = 3 primes[3] = 5 i*primes[j] = 65
j = 4 primes[4] = 7 i*primes[j] = 91
i = 14
j = 1 primes[1] = 2 i*primes[j] = 28
i = 15
j = 1 primes[1] = 2 i*primes[j] = 30
j = 2 primes[2] = 3 i*primes[j] = 45
i = 16
j = 1 primes[1] = 2 i*primes[j] = 32
i = 17
j = 1 primes[1] = 2 i*primes[j] = 34
j = 2 primes[2] = 3 i*primes[j] = 51
j = 3 primes[3] = 5 i*primes[j] = 85
i = 18
j = 1 primes[1] = 2 i*primes[j] = 36
i = 19
j = 1 primes[1] = 2 i*primes[j] = 38
j = 2 primes[2] = 3 i*primes[j] = 57
j = 3 primes[3] = 5 i*primes[j] = 95
i = 20
j = 1 primes[1] = 2 i*primes[j] = 40
i = 21
j = 1 primes[1] = 2 i*primes[j] = 42
j = 2 primes[2] = 3 i*primes[j] = 63
i = 22
j = 1 primes[1] = 2 i*primes[j] = 44
i = 23
j = 1 primes[1] = 2 i*primes[j] = 46
j = 2 primes[2] = 3 i*primes[j] = 69
i = 24
j = 1 primes[1] = 2 i*primes[j] = 48
i = 25
j = 1 primes[1] = 2 i*primes[j] = 50
j = 2 primes[2] = 3 i*primes[j] = 75
i = 26
j = 1 primes[1] = 2 i*primes[j] = 52
i = 27
j = 1 primes[1] = 2 i*primes[j] = 54
j = 2 primes[2] = 3 i*primes[j] = 81
i = 28
j = 1 primes[1] = 2 i*primes[j] = 56
i = 29
j = 1 primes[1] = 2 i*primes[j] = 58
j = 2 primes[2] = 3 i*primes[j] = 87
i = 30
j = 1 primes[1] = 2 i*primes[j] = 60
i = 31
j = 1 primes[1] = 2 i*primes[j] = 62
j = 2 primes[2] = 3 i*primes[j] = 93
i = 32
j = 1 primes[1] = 2 i*primes[j] = 64
i = 33
j = 1 primes[1] = 2 i*primes[j] = 66
j = 2 primes[2] = 3 i*primes[j] = 99
i = 34
j = 1 primes[1] = 2 i*primes[j] = 68
i = 35
j = 1 primes[1] = 2 i*primes[j] = 70
i = 36
j = 1 primes[1] = 2 i*primes[j] = 72
i = 37
j = 1 primes[1] = 2 i*primes[j] = 74
i = 38
j = 1 primes[1] = 2 i*primes[j] = 76
i = 39
j = 1 primes[1] = 2 i*primes[j] = 78
i = 40
j = 1 primes[1] = 2 i*primes[j] = 80
i = 41
j = 1 primes[1] = 2 i*primes[j] = 82
i = 42
j = 1 primes[1] = 2 i*primes[j] = 84
i = 43
j = 1 primes[1] = 2 i*primes[j] = 86
i = 44
j = 1 primes[1] = 2 i*primes[j] = 88
i = 45
j = 1 primes[1] = 2 i*primes[j] = 90
i = 46
j = 1 primes[1] = 2 i*primes[j] = 92
i = 47
j = 1 primes[1] = 2 i*primes[j] = 94
i = 48
j = 1 primes[1] = 2 i*primes[j] = 96
i = 49
j = 1 primes[1] = 2 i*primes[j] = 98
i = 50
j = 1 primes[1] = 2 i*primes[j] = 100
i = 51
i = 52
i = 53
i = 54
i = 55
i = 56
i = 57
i = 58
i = 59
i = 60
i = 61
i = 62
i = 63
i = 64
i = 65
i = 66
i = 67
i = 68
i = 69
i = 70
i = 71
i = 72
i = 73
i = 74
i = 75
i = 76
i = 77
i = 78
i = 79
i = 80
i = 81
i = 82
i = 83
i = 84
i = 85
i = 86
i = 87
i = 88
i = 89
i = 90
i = 91
i = 92
i = 93
i = 94
i = 95
i = 96
i = 97
i = 98
i = 99
i = 100
cnt=25
idx: 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
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97