|
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 62 63 64 65 66 67 68 69 70 71 72 73 74 |
#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <map> #include <stack> using namespace std; #define MAXN 1300000 bool prime[MAXN]; bool isPrime(int n){ for (int i = 2; i <= sqrt(n); i++) { if (n % i == 0) { return false; } } return true; } void genPrime(){ memset(prime, true, sizeof(prime)); for (int i = 2; i < MAXN; i++) { if (prime[i]) { if (isPrime(i)) { for (int k = 2; k * i < MAXN; k++) { prime[k*i] = false; } }else{ prime[i] = false; continue; } }else{ continue; } } } int main(){ genPrime(); int toQuery; while (cin >> toQuery) { if (!toQuery) { break; } int lbound = 0,rbound = 0; for (int i = toQuery; i >= 2; i--) { if (prime[i]) { lbound = i; break; } } for (int i = toQuery; i < MAXN; i++) { if (prime[i]) { rbound = i; break; } } cout << rbound - lbound << endl; } return 0; } |
埃氏筛法，没啥好说的嗯。
