#include <iostream> #include <vector> using namespace std; #define MAX_LEN 1000000 void getPrimeTable(bool *prime); int main() { bool prime[MAX_LEN+1]; long a, b; long i; vector<long> vec;//由于数可能很大 long t; getPrimeTable(prime); while (cin >> a >> b) { t = 0; for (i = a; i <= b; i++) { if (prime[i] == true) { t ++; } } vec.push_back(t); } i = 1; for (vector<long>::iterator it = vec.begin(); it != vec.end(); it++) { cout << "Case " << i << ":" << endl; cout << *it << endl; } return 0; } void getPrimeTable(bool *prime) { long i, j; for (i = 2; i <= MAX_LEN; i++) { prime[i] = true; } prime[0] = prime[1] = false; for (i = 2; i <= MAX_LEN; i++) { if (prime[i] == true) { for (j = 2 * i; j <= MAX_LEN; j += i) { prime[j] = false; } } } }