【代码超详解】HDU 2138 How many prime numbers? 有多少个质数？（质数埃筛打表 + 判定，31 ms）

一、题目描述

How many prime numbers

Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 27558 Accepted Submission(s): 9246（2019/11/11）

Problem Description

Give you a lot of positive integers, just to find out how many prime numbers there are.
给一堆正整数，找出其中有多少个质数。

Input

There are a lot of cases. In each case, there is an integer N representing the number of integers to find. Each integer won’t exceed 32-bit signed integer, and each of them won’t be less than 2.
有很多样例。每个样例中，有N个整数要判定。每个整数不超过32位有符号整数的范围，且不小于2。

Output

For each case, print the number of prime numbers you have found out.
对每个样例，输出所含质数的个数。

Sample Input

3
2 3 4

Sample Output

2

Author

wangye

Source

HDU 2007-11 Programming Contest_WarmUp

Recommend

威士忌 | We have carefully selected several similar problems for you: 2136 1431 2132 2139 2134

二、算法分析说明与代码编写指导

质数的埃氏筛法

1、用途：快速选出一定数量的质数。
2、算法内容：
埃拉托斯特尼（Eratosthenes）筛法（埃氏筛法） 要筛选出不大于n的质数，排除sqrt(n)以内全部质数的倍数即可。
（Eratosthenes（前276—前194），古希腊数学家）
设需要生成前若干个质数，prime数组用于存储已经验证为质数的数。
设a为当前正在验证是否为质数的正整数，t = sqrt(a)为需要试除的范围。
用已知的质数去除a，如果能整除，a就有除了1和a本身以外的因数，终止当前的判断，准备判断a+1。
为什么只用试除到t = sqrt(a)呢，因为因数是一对一对的，例如：
100 的因数有：1 2 4 5 10 20 25 50 100。我们发现，1 * 100 = 2 * 50 = 4 * 25 = 5 * 20 = 10 * 10。
如果验证到sqrt(a)后，还没有发现第3个a的因数，自然也不会再有了。
换句话说，还是以100为例子，如果找出了因数2，就可以计算出因数50。如果找到了因数4，就可以计算出因数25。
如果验证了某个数d不是a的因子，那么d的倍数也不是a的因子。
比如2不是 a 的因子，那么4 6 8 …… 都不用验证了。比如3不是 a 的因子，那么6 9 12 …… 都不用验证了。
如果要验证是否为a的因子的数d是质数，那么在之前验证过的数及其倍数都不是这个质数d的因数，也就是说d还没有用于验证过。
可见，用质数试除是不能避免的。对于合数来说，如果已知它的一个质因数不是a的因子，那么这个合数也不用再验证是否为a的因子。意即，要用这个合数去除a，就相当于用a的每个质因数去除a。如果某个质因数不能整除a，那么这个合数也不能整除a。
从几个角度都啰嗦完了，相信总有一种角度适合你的理解。

质数的判定

1、用途：迅速判定一个数是否为质数。
2、算法内容：
用埃氏筛法打质数表，打表结果保存在prime数组中。然后判断要验证是否为质数的整数x是否在表的范围内。如果是，在prime数组内二分搜索x，搜到就是质数，搜不到就不是。如果x超出了表的范围，就验证x是不是已经打表的质数的倍数。如果都不是，x就是质数。

3、代码实现：（含埃氏筛法打表，有时候int / unsigned的范围不够用，此时需要自己换类型）
要求：采用本参考代码时，需要先包含头文件algorithm和cmath（有的编译器的algorithm不含sqrt），且声明一个prime数组用于存储已经验证的质数，以及using namespace std; 传入的参数是需要生成的质数的数量。前2个质数2、3必须要先写入prime数组。额外建立一个变量_PTy，其类型与prime数组的类型相同，以便decltype关键字自动侦测类型。此外，x的类型不能大于prime数组的类型。
4、注意事项：
x不能超过最大已打表质数的平方，否则会返回错误的结果，从而WA。
5、时间复杂度：
设要判定的数为n。当n在质数打表范围时，二分搜索并返回搜索结果，时间复杂度为O(log n)（也可以写成O(ln n)）。
当n不在质数打表范围sqrt(n)时，最坏情况是需要用π(sqrt(n))个质数去验证（π(x)是不大于整数x的质数的数量）。所以判定一个数n是否为质数的时间复杂度不超过 。

三、AC 代码（31 ms）

#include<cstdio>
#include<algorithm>
#pragma warning(disable:4996)
using namespace std;
unsigned prime[4792] = { 2,3 }, _PTy, MaxPrime, * prime_end = prime + sizeof(prime) / sizeof(prime[0]);
inline void genprime() {
	decltype(_PTy) a = 4, t; bool flag;
	for (auto i = prime + 2; i < prime_end;) {
		t = sqrt(a); flag = true;
		for (auto j = prime; *j <= t; ++j)
			if (a % *j == 0) { flag = false; break; }
		if (flag) { *i = a, ++i; }
		++a;
	}
	MaxPrime = *(prime_end - 1);
}
inline bool isprime(const decltype(_PTy)& x) {
	if (x <= MaxPrime)return binary_search(prime, prime_end, x);
	else {
		decltype(_PTy) t = min((decltype(_PTy))sqrt(x), MaxPrime);
		for (auto j = prime; *j <= t; ++j)
			if (x % *j == 0)return false;
		return true;
	}
}
int main() {
	genprime(); unsigned N, X, C;
	for (;;) {
		if (scanf("%u", &N) == EOF)return 0;
		++N, C = 0;
		while (--N) {
			scanf("%u", &X);
			if (isprime(X))++C;
		}
		printf("%u\n", C);
	}
}