素数水题。题意:给你一个不大于一万的整数n,求有多少种方案可以把n写成若干个连续素数的和。
我的解题思路:把不大于一万的素数都筛出来,存储成前n个素数的和这样的形式。然后枚举每一个方案,把对应方案计算的和所对应的方案次数加一就可以了。存储好一万个数的答案。如果说一万以内的素数个数是k,那么这个枚举的复杂度是O((1+k)*k/2)。也就是k平方的复杂度,时间是够了。0ms水过。
我的解题代码:
#include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cmath> #include <algorithm> #include <vector> using namespace std; const int N = 10002; bool isprime[N]; int primes[N], pn; int ans[N]; int n; void InitRead(); void FastSieve(int maxn); int main() { InitRead(); while (~scanf("%d", &n)) { if (n == 0) break; printf("%d\n", ans[n]); } return 0; } void InitRead() { memset(isprime, true, sizeof(isprime)); memset(ans, 0, sizeof(ans)); isprime[0] = isprime[1] = false; pn = 0; FastSieve(N - 1); int temp[N]; //存储前n个素数的和 temp[0] = 0; for (int i=0; i<pn; ++i) { temp[i+1] = temp[i] + primes[i]; } for (int i=0; i<pn; ++i) { for (int j=i+1; j<=pn; ++j) //以primes[i]作为左端点来枚举 { if (temp[j] - temp[i] >= N) break; //优化一下,如果超过一万了就可以跳出了 ans[temp[j] - temp[i]]++; } } return; } void FastSieve(int maxn) { for (int i=2; i<=maxn; ++i) { if (isprime[i]) primes[pn++] = i; for (int j=0; j<pn; ++j) { if (i * primes[j] > maxn) break; isprime[i * primes[j]] = false; if (i % primes[j] == 0) break; } } return; }