筛法

发表于 更新于 分类于 ， 阅读次数： 本文字数： 1.1k 阅读时长 ≈ 4 分钟

\(\qquad\!\!\)整理一些 OI 中常用的筛法：

  • 1、埃拉托斯特尼筛法：

\(\qquad\!\!\)例题：

\(\qquad\!\!\)给定一个数 \(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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<bits/stdc++.h>
#define in inline
#define re register
const int N=100;
const double eps=1e-6;
using namespace std;
int n;
bool prime[N]; 
in int qread()
{
    int x=0,y=1;
    int ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
		{
			y=-1;
		}
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*y;
}
in void qwrite(re int x)
{
	if(x<0)
	{
		putchar('-');
		qwrite(-x);
	}
	else
	{
		if(x>9)
		{
			qwrite(x/10);
		}
		putchar(x%10+'0');
	}
	return ;
}
in void ass(re int x)
{
	memset(prime,1,sizeof(prime));
	prime[0]=0;
	prime[1]=0;
	int t=sqrt(x)+eps;
	for(re int i=2;i<=t;i++)
	{
		if(prime[i])
		{
			for(re int j=(i<<1);j<=x;j+=i)
			{
				prime[j]=0;
			}
		}
	}
}
int main()
{
	n=qread();
	ass(n);
	qwrite(prime[n]);
	putchar('\n');
	return 0;
}
  • 2、欧拉筛法：

\(\qquad\!\!\)欧拉筛法是一种在线性时间复杂度内求出 \(1-n\) 中所有的素数的筛法，通常被称为线性筛：

\(\qquad\!\!\)例题：

\(\qquad\!\!\)P3383 【模板】线性筛素数：

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include<bits/stdc++.h>
#define in inline
#define re register
const int N=100000010;
using namespace std;
int n,q,k; 
bool prime[N];
int _prime[N],cnt;
in int qread()
{
    int x=0,y=1;
    int ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
		{
			y=-1;
		}
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*y;
}
in void qwrite(re int x)
{
	if(x<0)
	{
		putchar('-');
		qwrite(-x);
	}
	else
	{
		if(x>9)
		{
			qwrite(x/10);
		}
		putchar(x%10+'0');
	}
	return ;
}
in void oss(re int x)
{
	memset(prime,1,sizeof(prime));
	prime[0]=0;
	prime[1]=0;
	for(re int i=2;i<=x;i++)
	{
		if(prime[i])
		{
			_prime[++cnt]=i;
		}
		for(re int j=1;j<=cnt&&i*_prime[j]<=x;j++)
		{
			prime[i*_prime[j]]=0;
			if(!(i%_prime[j]))
			{
				break;
			}
		}
	}
} 
int main()
{
	n=qread();
	oss(n);
	q=qread();
	while(q--)
	{
		k=qread();
		qwrite(_prime[k]);
		putchar('\n');
	}
	return 0;
}
  • 3、线性筛欧拉函数：

\(\qquad\!\!\)例题：

\(\qquad\!\!\)P2158 [SDOI2008]仪仗队：

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include<bits/stdc++.h>
#define in inline
#define re register
const int N=40010;
using namespace std;
int n,cnt,ans;
bool prime[N];
int _prime[N],phi[N];
in int qread()
{
    int x=0,y=1;
    int ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
		{
			y=-1;
		}
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*y;
}
in void qwrite(re int x)
{
	if(x<0)
	{
		putchar('-');
		qwrite(-x);
	}
	else
	{
		if(x>9)
		{
			qwrite(x/10);
		}
		putchar(x%10+'0');
	}
	return ;
}
in void oss(re int x)
{
	memset(prime,1,sizeof(prime));
	prime[0]=0;
	prime[1]=0;
	phi[1]=1;
	for(re int i=2;i<=x;i++)
	{
		if(prime[i])
		{
			_prime[++cnt]=i;
			phi[i]=i-1;
		}
		for(re int j=1;j<=cnt&&i*_prime[j]<=x;j++)
		{
			prime[i*_prime[j]]=0;
			if(!(i%_prime[j]))
			{
				phi[i*_prime[j]]=phi[i]*_prime[j];
				break;
			}
			else
			{
				phi[i*_prime[j]]=phi[i]*(_prime[j]-1);
			}
		}
	}
	return ;
} 
int main()
{
	n=qread();
	if(n==1||n==0)
	{
		putchar('0');
		putchar('\n');
		return 0;
	}
	oss(n);
	for(re int i=2;i<=n-1;i++)
	{
		ans+=phi[i]*2;
	}
	ans+=3;
	qwrite(ans);
	putchar('\n');
	return 0;
}
  • 4、线性筛约数个数：

\(\qquad\!\!\)例题：

\(\qquad\!\!\)求出 \(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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
//线性筛约数个数 
#include<bits/stdc++.h>
#define in inline
#define re register
const int N=N;
using namespace std;
int n,cnt;
bool prime[N];
int _prime[N],tot[N],num[N];
in int qread()
{
    int x=0,y=1;
    int ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
		{
			y=-1;
		}
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*y;
}
in void qwrite(re int x)
{
	if(x<0)
	{
		putchar('-');
		qwrite(-x);
	}
	else
	{
		if(x>9)
		{
			qwrite(x/10);
		}
		putchar(x%10+'0');
	}
	return ;
}
in void oss(re int x)
{
	memset(prime,1,sizeof(prime));
	prime[0]=0;
	prime[1]=0;
	tot[1]=1;
	num[1]=1;
	for(re int i=2;i<=x;i++)
	{
		if(prime[i])
		{
			_prime[++cnt]=i;
			tot[i]=2;
			num[i]=1;
		}
		for(re int j=1;j<=cnt&&i*_prime[j]<=x;j++)
		{
			prime[i*_prime[j]]=0;
			if(!(i%_prime[j]))
			{
				tot[i*_prime[j]]=tot[i]/(num[i]+1)*(num[i]+2);
				num[i*_prime[j]]=num[i]+1;
				break;
			}
			else
			{
				num[i*_prime[j]]=1;
				tot[i*_prime[j]]=(tot[i]<<1);
			}
		}
	}
	return ;
} 
int main()
{
	n=qread();
	oss(n+1);
	qwrite(tot[n]);
	putchar('\n');
	return 0;
}
  • 5、线性筛约数和：

\(\qquad\!\!\)例题：

\(\qquad\!\!\)求出 \(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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include<bits/stdc++.h>
#define in inline
#define re register
const int N=N;
using namespace std;
int n,cnt;
bool prime[N];
int _prime[N],sum[N],tot[N];
in int qread()
{
    int x=0,y=1;
    int ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
		{
			y=-1;
		}
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*y;
}
in void qwrite(re int x)
{
	if(x<0)
	{
		putchar('-');
		qwrite(-x);
	}
	else
	{
		if(x>9)
		{
			qwrite(x/10);
		}
		putchar(x%10+'0');
	}
	return ;
}
in void oss(re int x)
{
	memset(prime,1,sizeof(prime));
	prime[0]=0;
	prime[1]=0;
	sum[1]=1;
	for(re int i=2;i<=x;i++)
	{
		if(prime[i])
		{
			_prime[++cnt]=i;
			sum[i]=i+1;
			tot[i]=1;
		}
		for(re int j=1;j<=cnt&&i*_prime[j]<=x;j++)
		{
			prime[i*_prime[j]]=0;
			if(!(i%_prime[j]))
			{
				sum[i*_prime[j]]=sum[i]*_prime[j]+tot[i];
				tot[i*_prime[j]]=tot[i];
				break;
			}
			else
			{
				sum[i*_prime[j]]=sum[i]*(_prime[j]+1);
				tot[i*_prime[j]]=sum[i];
			}
		}
	}
	return ;
} 
int main()
{
	n=qread();
	oss(n+1);
	qwrite(sum[n]);
	putchar('\n');
	return 0;
}