线性筛
埃拉特斯托尼筛
时间复杂度 O(NloglogN)
空间复杂度 O(N)
欧拉筛
时间复杂度 O(N)
空间复杂度 O(N)
时间复杂度证明：
设合数𝑛最小的质因数为𝑝，它的另一个大于𝑝的质因数为𝑝′，令
𝑛 = 𝑝𝑚 = 𝑝′𝑚′
观察上面的程序逻辑，可以发现𝑗循环到质因数𝑝时合数𝑛第一次被标记，若也被𝑝′标记，则是在这之前（因为𝑚′ < 𝑚），考虑𝑖循环到𝑚′，注意到𝑛 = 𝑝𝑚 = 𝑝′𝑚′且𝑝, 𝑝′为不同的质数，因此𝑝|𝑚′，所以当𝑗循环到质数𝑝后结束，不会循环到𝑝′，这就说明不会被𝑝′筛去。
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
| #include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#define ll long long
#define MAXN 50000009
using namespace std;
ll check[MAXN],prime[MAXN];
ll getprime(){
ll tot=0;
memset(check,false,sizeof(check));
check[0]=check[1]=true;
for(int i=2;i<MAXN;i++){
if(!check[i]){
prime[tot++]=i;
for(int j=i<<1;j<MAXN;j+=i){
check[j]=true;
}
}
}
return tot;
}
ll getprime_Euler(){
ll tot=0;
memset(check,false,sizeof(check));
check[0]=check[1]=true;
for(int i=2;i<MAXN;i++){
if(!check[i]){
prime[tot++]=i;
}
for(int j=0;j<tot;j++){
if(i*prime[j]>MAXN){
break;
}
check[i*prime[j]]=true;
if(i%prime[j]==0){
break;
}
}
}
return tot;
}
int main()
{
ll a,b;
a=getprime_Euler();
b=getprime();
}
|
积性函数
考虑一个定义域为N+的函数𝑓，对于任意两个互质的正整数𝑎, 𝑏，均满足𝑓(𝑎𝑏)=𝑓(𝑎)𝑓(𝑏)，则函数𝑓被称为积性函数。
假如对于任意两个正整数𝑎, 𝑏，都有𝑓(𝑎𝑏)=𝑓(𝑎)𝑓(𝑏)，函数𝑓也被称为完全积性函数。
容易看出，对于任意积性函数（完全积性函数），𝑓(1) = 1。
考虑一个大于1的正整数𝑁，设
𝑁 = 𝑝𝑖𝛼𝑖
其中𝑝𝑖为互不相同的质数，那么对于一个积性函数𝑓，𝑓(𝑁)=𝑓(𝑝𝑖^𝛼𝑖)= 𝑓(𝑝𝑖)^𝛼𝑖
rane如果𝑓还满足完全积
性，则𝑓 𝑁 = 𝑓 𝑝𝑖
