筛素数的水题。题意:给一个整数n,求n后一个素数和前一个素数的差值,如果n是素数时输出0。
我的解题思路:数据范围不太大,不过为了保险起见还是要离线处理。筛出范围内的素数表,然后就可以一次性算出所有数的答案,保存起来,这样查询速度会很快。
我的解题代码:
#include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cmath> #include <algorithm> #include <vector> #include <queue> #include <stack> using namespace std; const int N = 1299710; int isprime[N]; //存储答案,素数则为0,非素数则为答案,0和1特殊 int primes[N], pn; int n; void InitRead(); void DataProcess(); void FastSieve(int maxn); int main() { InitRead(); while (~scanf("%d", &n)) { if (n == 0) break; DataProcess(); } stack<int> s; return 0; } void InitRead() { memset(isprime, 0, sizeof(isprime)); isprime[0] = isprime[1] = -1; pn = 0; FastSieve(N-1); for (int i=1; i<pn; ++i) { for (int j=primes[i-1]+1; j<primes[i]; ++j) { isprime[j] = primes[i] - primes[i-1]; } } return; } void DataProcess() { printf("%d\n", isprime[n]); return; } void FastSieve(int maxn) { for (int i=2; i<=maxn; ++i) { if (isprime[i] == 0) primes[pn++] = i; for (int j=0; j<pn; ++j) { if (i * primes[j] > maxn) break; isprime[i * primes[j]] = 1; if (i % primes[j] == 0) break; } } return; }