LightOj 1259 Goldbach`s Conjecture 素数筛法

2019-11-08 02:32:01

字体：大中小

来源：转载

供稿：网友

链接： LOJ 1259

题解

一般素数筛法，注意空间复杂度

code

#include<cstdio>#include<cstring>#include<iostream>using namespace std;const int N = 10000000;int PRime[N / 10 + 5]; bool f[N + 5];/**bool型省空间*/void getPrime(){ memset(prime, 0, sizeof prime); memset(f, 0, sizeof f); /**prime[0] = 0;*/ f[1] = 1; for(int i = 2; i < N; ++i){/**素数筛法*/ if(!f[i]){ prime[++prime[0]] = i; } for(int j = 2; i * j < N; ++j) f[i * j] = 1; }}int main(){ int t, n; cin >> t; getPrime(); for(int kase = 1; kase <= t; ++kase){ int ans = 0; cin >> n; for(int i = 1; prime[i] * 2 <= n; ++i){ if(!f[n - prime[i]]) ++ans; } cout << "Case " << kase << ": " << ans << endl; } return 0;}

上一篇：算法与数据结构【三】——栈的C语言实现

下一篇：搜索旋转数组