欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【代码超详解】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

  1. 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, …

二、算法分析说明与代码编写指导

【代码超详解】LightOJ 1259 Goldbach`s Conjecture(欧拉筛)【代码超详解】LightOJ 1259 Goldbach`s Conjecture(欧拉筛)

三、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;
}
相关标签: ACM-ICPC 详解