mydcwfy's Blog

筛质数

Posted on
Symbols count in article: 3.6k Reading time ≈ 8 mins.

比较简单的前置知识。

筛质数

1. 埃氏筛法

比较简单，算法核心就是直接将所有该质数的所有倍数筛掉。

1
2
3
4
5
6
7
for (int i=2;i<=n;++i)
{
    if (isprime[i]) prime[cnt++]=i;
    else break;
    for (int j=2*i;j<=n;j+=i)
        	isprime[j]=false;
}

时间复杂度为 $O(n*(1/2+1/3+…))=O(n \log \log n)$。

2. 线性筛法

先看代码。

1
2
3
4
5
6
7
8
9
for (int i=2;i<=n;++i)
{
    if (isprime[i]) prime[cnt++]=i;
    for (int j=0;j<cnt&&i*prime[j]<=n;++j)
    {
        isprime[i*prime[j]]=false;
        if (i%prime[j]==0) break;
    }
}

可以证明，每一个合数都只会被它的最小质因数筛掉。

时间复杂度为 $O(n)$。

3. 例题

T1：哥德巴赫猜想

题目传送门 Luogu

直接枚举所有质数，看减后的数是不是素数即可。

代码略。

T2：Sherlock and his girlfriend

题目传送门 Luogu(RemoteJudge:Codeforces)

可以发现，该限制条件是质数与合数之间，不可能是质数与质数之间，合数与合数之间。

所以该图为二分图（按限制条件建边），答案不超过二。

只要有合数，那么答案必然为 2。

即可。

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=1e5+10;
int prime[N],cnt;
bool isprime[N];

void init()
{
	for (int i=2;i<N;++i) isprime[i]=true;
	for (int i=2;i<N;++i)
	{
		if (isprime[i]) prime[cnt++]=i; 
		for (int j=0;j<cnt&&i*prime[j]<N;++j)
		{
			isprime[i*prime[j]]=false;
			if (!(i%prime[j])) break;
		}
	}
	return ;
}

int main()
{
	init();
	int n;cin>>n;
	if (n>=3) puts("2");
	else puts("1");
	for (int i=1;i<=n;++i)
		if (isprime[i+1]) printf("1 ");
		else printf("2 ");
	return 0;
}

T3：质数距离

题目传送门 AcWing

这道题，需要我们去改进该算法。

因为所有算法都是从 1 开始的，且至少要 $O(n)$。

仔细分析，我们发现，任何一个数，都有一个质数 $\leq \sqrt n$。

所以，我们可以先处理出所有 $\leq \sqrt n$ 的质数，然后用这些数去筛 $[L,R]$。

复杂度为 $O((R-L)\log\log R)$。

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
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#define mp make_pair
#define x first
#define y second
using namespace std;

typedef long long ll;
typedef pair<long long,long long> PLL;
const int N=50000,T=1e6+10,INF=1e9;
int prime[N],cnt;
bool isprime[N];
bool vis[T];
ll l,r;

void init()
{
    memset(isprime,true,sizeof isprime);
    for (int i=2;i<N;++i)
    {
        if (isprime[i]) prime[cnt++]=i;
        for (int j=0;j<cnt&&prime[j]*i<N;++j)
        {
            isprime[i*prime[j]]=false;
            if (!(i%prime[j])) break;
        }
    }
}

int main()
{
    init();
    while (cin>>l>>r)
    {
        memset(vis,0,sizeof vis);
        for (int i=0;i<cnt;++i)
        {
            ll p=prime[i],low=(l+p-1)/p,high=r/p;
            for (int j=max((ll)2,low);j<=high;++j)
                vis[p*j-l]=true;
        }
        ll maxn=0,minx=INF;
        PLL maxp,minp;
        for (int i=0,last=-1;i<=r-l;++i)
            if (!vis[i]&&i+l>=2)
            {
                if (~last)
                {
                    if (maxn<i-last) maxn=i-last,maxp=mp(last+l,i+l);
                    if (minx>i-last) minx=i-last,minp=mp(last+l,i+l);
                }
                last=i;
            }
        if (maxn==0) puts("There are no adjacent primes.");
        else printf("%lld,%lld are closest, %lld,%lld are most distant.\n"
            ,minp.x,minp.y,maxp.x,maxp.y);
    }
}

T4：阶乘分解

题目传送门 AcWing

将所有的质数的次数存下来即可。

$n!$ 中 $p$ 的次数为 $\dfrac{n}{p}+\dfrac{n}{p^2}+\dfrac{n}{p^3}…$。

因为如果是 $p^k$ 的倍数，会在 $\dfrac{n}{p},\dfrac{n}{p^2},..\dfrac{n}{p^k}$ 都加过一遍。

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
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;

typedef long long ll;
const int N=1e6+10;

int prime[N],n,cnt;
ll ti[N];
bool isprime[N];

void init()
{
	memset(isprime,true,sizeof isprime);
	for (int i=2;i<N;++i)
	{
		if (isprime[i]) prime[cnt++]=i;
		for (int j=0;j<cnt&&prime[j]*i<N;++j)
		{
			isprime[i*prime[j]]=false;
			if (!(i%prime[j])) break;
		}
	}
}

int main()
{
	init();
	cin>>n;
	for (int i=0;i<cnt;++i)
	{
		int &p=prime[i];
		ll tot=p;
		while (tot<=(ll)n) ti[i]+=(ll)n/tot,tot*=p;
	}
	for (int i=0;i<cnt&&prime[i]<=n;++i) printf("%d %d\n",prime[i],ti[i]);
	return 0;
}