1.题目描述：点击打开链接
2.解题思路：根据题意可知最大的素数在int范围内，可以先算出1299709以内的所有素数，随后二分查找n附近的素数的位置即可。
3.代码：
?
#define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define N 1300000 int vis[N]; vector primes; void init() { int m = sqrt(N + 0.5); for (int i = 2; i <= m;i++) if (!vis[i]) for (int j = i*i; j < N; j += i) vis[j] = 1; for (int i = 2; i <= N;i++) if (!vis[i]) primes.push_back(i); } int main() { //freopen("test.txt", "r", stdin); int n; init(); while (scanf("%d", &n) != EOF&&n) { if (!vis[n])cout << 0 << endl; else { int L = 0, R = 100000; while (L < R) { int m = L + (R - L) / 2; if (primes[m] > n)R = m; else L = m + 1; } cout << primes[L] - primes[L - 1] << endl; } } return 0; }