【題目敘述】https://zerojudge.tw/ShowProblem?problemid=e530
【解題想法】質數表
- 題目給定 k，
- 如果 k 是質數，答案為 0。
- 如果 k 不是質數，找出比 k 大的質數 p2，比 k 小的質數 p1，答案為 p2 – p1。
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 1299709+5;
int p[maxn];
vector <int> v;
int main() {
for (int i = 2; i < maxn; i++){
if (p[i] == 0){
for (int j = i+i; j < maxn; j+=i){
p[j] = 1;
}
v.push_back(i);
}
}
int k;
while (cin >> k){
if (k == 0) break;
auto it = lower_bound(v.begin(), v.end(), k);
int p2 = *it;
if (p2 == k) cout << "0\n";
else {
int p1 = *(--it);
cout << p2 - p1 << "\n";
}
}
return 0;
}