蓝桥杯算法提高VIP-找素数 （C++代码）

解题思路:

        请看 1790。

参考代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

bool isprime(LL num) {
	if (num < 2) return false;
	for (int i = 2; i <= sqrt(num); i++)
		if (num%i == 0)
			return false;
	return true;
}

int main() {
	LL start, end;
	bool primetable[1000003] = { false };
	cin >> start >> end;
	if (end < 2)
		cout << 0 << endl;
	else {
		if (start < 2)
			start = 2;

		LL limits = (LL)sqrt(end);
		for (LL i = 2; i <= limits; i++)
			if (isprime(i)) {
				LL N = start / i > 2 ? start / i : 2;
				for (; N*i <= end; N++)
					if (N*i >= start)
						primetable[N*i - start] = true;
			}

		int total = 0;
		for (LL i = 0; i <= end - start; i++)
			if (!primetable[i])
				total++;
		cout << total << endl;
	}
}