lightoj 1197 Help Hanzo 素数筛法

缘起

筛法是算法的重要的知识, 故学之, 选择了 lightoj 1197 Help Hanzo

来练习筛法模板。

分析

题目很裸

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
给定正整数a和b, 求[a,b]中素数的个数.

【输入】
首先输入T(<=200)表示样例的个数, 然后每行2个正整数a和b, (1 ≤ a ≤ b < 231, b - a ≤ 100000)

【输出】
对于每个case，输出[a,b]之间的素数的个数

【样例输入】
3
2 36
3 73
3 11

【样例输出】
Case 1: 11
Case 2: 20
Case 3: 4

【限制】
Time Limit: 2 second(s)	
Memory Limit: 32 MB

因为b的范围太大了，没办法直接用（线性）筛法求出.

办法1: 因为int范围的整数如果不是质数的话, 则它的一个素数因子一定在5w（代码中是1<<16=65536）内(5w*5w=25亿>int最大值). 所以首先使用线性筛法模板处理出 5w以内全部素数, 然后对于 [a,b]范围内的每个x, 只需要判断x能否被5w内的任意一个素数整除即可，如果能, 就不是素数，如果不能, 则就是素数. 于是写出相应代码如下

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
#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#include <math.h>
#define LOCAL

int a,b;

bool isprime[1<<16]; // isprime为true表示是素数, false表示不是素数
int primes[1<<16], num; // num 是 1<<16内的素数的个数

void sieve() // 线性筛法
{
	memset(isprime,true, sizeof(isprime)); //预设全部是素数
	for (int i = 2; i<=(1<<16); i++) if (isprime[i]) for (int j = (i<<1); j<(1<<16); j+=i) isprime[j] = false; // 最后 isprime[i]为true的就是素数
	for (int i = 2; i<=(1<<16);i++) if (isprime[i]) primes[num++] = i; // 得出 1<<16内的全体素数
}

bool ok(int x) // x是不是素数
{
	if (x==2) return true;
	int limit = ceil(sqrt(1.0*x));
	for (int i = 0; i<num && primes[i]<=limit;i++)
	{
		if (!(x%primes[i]))
		{
			return false;
		}
	}
	return true;
}

int solve()
{
	int ans = 0;
	for (int i = a; i<=b;i++)
	{
		if (ok(i)) 
		{
			ans++;
		}
	}
	return ans;
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	sieve(); // 预处理
	int t;
	scanf("%d", &t);
	for (int i = 1; i<=t; i++)
	{
		scanf("%d%d", &a, &b);
		printf("Case %d: %d\n", i, solve());
	}
	return 0;
}

不幸的是 Time Limit Exceeded

所以得想其他办法——其实超时的根源在于对于每个i都要遍历一遍所有的素数（大约5000左右个），而[a,b]有10w个数，则复杂度是O(10w*5000) 就是亿量级的, 自然会超时. 正确的解法依旧是处理出5w以内全部素数. 然后只需要使用这些素数作为筛子去筛[a,b]范围内的素数（是素数就是true, 不是就是false）

例如对于素数p, 则[a,b]范围内的能被p整除的第一个数是不难求出的, 然后逐个遍历用筛法来筛[a,b]这个区间，这样做的复杂度降低为 O(10w*sigma(1/p), p为所有不超过5w的素数，5k个), 自然这种复杂度低得多.

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
#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#include <math.h>
#define LOCAL
typedef long long LL;

LL a,b;

bool isprime[50005], isprime2[100005]; // isprime为true表示是素数, false表示不是素数, isprime2[i]用于表示a+i是否是素数
LL primes[50005]; // primes 是 50000内的素数
LL num; // num 是 50000内的素数的个数

void sieve() // 线性筛法
{
	memset(isprime,true, sizeof(isprime)); //预设全部是素数
	for (LL i = 2; i<=50000; i++) if (isprime[i]) for (LL j = (i<<1); j<=50000; j+=i) isprime[j] = false; // 最后 isprime[i]为true的就是素数
	for (LL i = 2; i<=50000;i++) if (isprime[i]) primes[num++] = i; // 得出 50000内的全体素数
}

LL solve()
{
	LL ans = 0;
	memset(isprime2, true, sizeof(isprime2));
	for (LL i = 0; i<num; i++)
	{
		LL start = (a%primes[i]?(a/primes[i]+1)*primes[i]:a)-a; // 筛的起点, 注意, 这里可能越int的界,所以要用long,在这里wa了N次
		if (start > b-a) continue; // 如果超出范围的话
		isprime2[start] = (a+start<=50000?isprime[a+start]:false);
		for (int j = (start+primes[i]); j<=b-a; j+=primes[i]) isprime2[j] = false;
	}
	for (LL i = 0; i<=b-a; i++)if (isprime2[i]) ans++; // 如果 a+i 是素数
	return ans;
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	freopen("d:\\my.out", "w", stdout);
#endif
	sieve(); // 预处理出5w内的素数保存进primes
	LL t;
	scanf("%lld", &t);
	for (LL i = 1; i<=t; i++)
	{
		scanf("%lld%lld", &a, &b);
		if (a==1) a=2;
		if (b<a)
		{
			printf("Case %lld: %d\n", i, 0);
			continue;
		}
		printf("Case %lld: %lld\n", i, solve());
	}
	return 0;
}

ac情况

1549652 2019-08-11 19:19:34 1197 - Help Hanzo C++ 0.104 1692 Accepted