LightOJ 1259 Goldbach`s Conjecture

本文主要是介绍LightOJ 1259 Goldbach`s Conjecture，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：
给出一个偶数n，求出有几对素数的和等于n；即素数a，b其中(a <=b < n)    问有几对a+b = n。
分析：
一开始用素数打表，开个1e7的int数组存是否为素数， 最后再遍历 这些素数，是否存在 b =(n-这个数),  如果b还是素数，并且b >= a,则存在一组，ans++。
一开始内存超限了几次，后来学到了，开的数组可以开个bool类型的，bool 每一个只占一个字节，而int占四个字节，内存一下就变成了1/4。
代码：

#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;typedef long long ll;
const int N = 10000010;
bool b[N] = {1, 1, 0};
int prim[700000];
void dabiao()
{int t = 1;for(int i = 2; i < N; i++){if(!b[i]){prim[t++] = i;for(int j = i + i; j <= N; j += i)b[j] = 1;}}
}
int main()
{int t; scanf("%d", &t);int kase = 1;dabiao();while(t--){int n, ans = 0; scanf("%d", &n);for(int i = 1; prim[i] <= n/2; i++){if(b[n-prim[i]] == 0) ans++;}printf("Case %d: %d\n", kase++, ans);}return 0;
}

这篇关于LightOJ 1259 Goldbach`s Conjecture的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---