F - Goldbach`s Conjecture
题目链接：https://vjudge.net/problem/LightOJ-1259#author=yyb
题目大意：
T组询问，每组询问是一个偶数n，验证哥德巴赫猜想，回答n=a+b，且a，b(a<=b)是质数的方案个数。
解题思路：
欧拉筛，遍历到 $2^{*}$prime$[j]<=n$ ，其中令$a=prime[j]，b=n-prime[j]$，判断b是否为质数即可。
代码：
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define debug(a) cout<<#a<<":"<<a<<endl; 4 typedef long long ll; 5 const int INF=1e9+7; 6 const ll N=1e7+7; 7 const int mod=1e9+7; 8 int T,n; 9 bool isprime[N]; 10 int prime[N/10]; 11 int m; 12 void primes(){ 13 memset(isprime,false,sizeof(isprime)); 14 isprime[1]=true; 15 m=1; 16 for(ll i=2;i<N;i++){ 17 if(!isprime[i]){ 18 prime[m++] = i; 19 for(ll j=i*i;j<N;j+=i){ 20 isprime[j] = true; 21 } 22 } 23 } 24 } 25 int main(){ 26 primes(); 27 cin>>T; 28 int a,num; 29 for(int i=1;i<=T;i++){ 30 scanf("%d",&a); 31 num=0; 32 for(int j=1;2*prime[j]<=a;j++){ 33 if(!isprime[a-prime[j]]){ 34 num++; 35 } 36 } 37 printf("Case %d: %d\n",i,num); 38 } 39 return 0; 40 }
原文链接: https://www.cnblogs.com/meanttobe/p/12397272.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/333076
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
