【代码超详解】LightOJ 1259 Goldbach`s Conjecture(欧拉筛)
程序员文章站
2022-07-14 09:46:18
...
一、题目描述
Goldbach’s conjecture is one of the oldest unsolved problems in number theory and in all of mathematics. It states:
Every even integer, greater than 2, can be expressed as the sum of two primes [1].
Now your task is to check whether this conjecture holds for integers up to 107.
Input
Input starts with an integer T (≤ 300), denoting the number of test cases.
Each case starts with a line containing an integer n (4 ≤ n ≤ 107, n is even).
Output
For each case, print the case number and the number of ways you can express n as sum of two primes. To be more specific, we want to find the number of (a, b) where
1) Both a and b are prime
2) a + b = n
3) a ≤ b
Sample Input
2
6
4
Sample Output
Case 1: 1
Case 2: 1
Note
- An integer is said to be prime, if it is divisible by exactly two different integers. First few primes are 2, 3, 5, 7, 11, 13, …
二、算法分析说明与代码编写指导
三、AC 代码
1:
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<bitset>
#pragma warning(disable:4996)
using namespace std;
unsigned prime[664579], _PrimeTy, MaxPrime, * prime_end = prime; bitset<10000001> notprime;
inline void gen_prime() {
decltype(_PrimeTy) n = notprime.size() - 1, m = n / 2, L; notprime[0] = notprime[1] = true;
for (decltype(_PrimeTy) i = 2; i <= m; ++i) {
if (!notprime[i]) { *prime_end = i, ++prime_end; }
L = n / i;
for (auto j = prime; j != prime_end && *j <= L; ++j) {
notprime[i * *j] = true; if (i % *j == 0)break;
}
}
for (decltype(_PrimeTy) i = m + 1; i <= n; ++i)
if (!notprime[i]) { *prime_end = i, ++prime_end; }
MaxPrime = *(prime_end - 1);
}
unsigned t, m, n, c;
int main() {
gen_prime();
scanf("%u", &t);
for (unsigned i = 1; i <= t; ++i) {
scanf("%u", &n); c = 0; m = n / 2;
for (auto j = prime; *j <= m; ++j) {
if (notprime[n - *j] == false)++c;
}
printf("Case %u: %u\n", i, c);
}
return 0;
}
2、这里附上一份时间只有 213 ms 的代码(第 1 份运行耗时约 521 ms),至于该代码为何跑得这么快,原因不明确:
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<queue>
#include<stack>
#include<string>
#include<vector>
#include<map>
#include<set>
using namespace std;
#define lowbit(x) (x&(-x))
typedef long long LL;
const int maxn = 100005;
const int inf=(1<<28)-1;
#define maxp 10000005
bool notprime[maxp];
int primes[700005];
void get_prime()
{
notprime[1]=true;
for(int i=2;i<maxp;++i)
if(!notprime[i])
{
primes[++primes[0]]=i;
for(LL j=(LL)i*i;j<maxp;j+=i)
notprime[j]=true;
}
}
int main()
{
get_prime();
//printf("%d\n",primes[0]);
int T,Case=0;
scanf("%d",&T);
while(T--)
{
int n;
scanf("%d",&n);
int Ans=0;
for(int i=1;primes[i]<=n/2;++i)
if(!notprime[n-primes[i]]) Ans++;
printf("Case %d: %d\n",++Case,Ans);
}
return 0;
}