NC16434. 哥德巴赫猜想验证
描述
小C在进行一项伟大的事业，他想证明哥德巴赫猜想！
经过一节课的冥思苦想，他决定放弃了。。。
(小C：我是绝对不会告诉你我是在哪节课上想的，呵呵)
小C后来验证了一下哥德巴赫猜想，惊奇地发现对于一个大偶数，满足条件的质数对的数目比想象中的多很多。而他原本认为，哥德巴赫猜想难以证明的原因是对于大偶数，满足条件的数目应该很少。 
上图横坐标为100000以内的偶数，纵坐标为对应的质数对的数目
哥德巴赫猜想如下：任一大于2的偶数都可写成两个质数之和。
若x+y=m满足m为偶数，x<=y，且x,y均为质数，则称(x,y)是关于m的质数对。
本题目需要求出n以内的质数对的数目。
输入描述
第一行输入n（n保证为正偶数,n<=1000000）。
输出描述
输出一行，为n以内的的质数对的数目。
示例1
输入:
8
输出:
3
说明:
2+2=4，3+3=6,3+5=8，有(2,2),(3,3),(3,5)共三对。pypy3(pypy3.6.1) 解法, 执行用时: 205ms, 内存消耗: 56344K, 提交时间: 2020-09-23 20:34:46
w=[0 for x in range(0,1000005)]
q=[]
vis=[False for x in range(0,1000005)]
n=sum(map(int,input().split()))
try:
ans=0
for i in range(2,n+1,1):
if vis[i]==True:
w[i]=w[i-1]
continue
if i!=2:
w[i]=w[i-1]+1
q.append(i)
for j in range(i+i,n+1,i):
vis[j]=True
for i in range(len(q)):
if q[i]<=n//2:
ans+=w[q[i]]
else:
ans+=w[n-q[i]]
if n>=4:
ans+=1
print(ans)
except:
pass
C++(clang++11) 解法, 执行用时: 11ms, 内存消耗: 4608K, 提交时间: 2021-06-23 17:10:54
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int cnt,st[N],p[N];
void init(int n)
{
for (int i=2;i<=n;i++){
if(!st[i]) p[cnt++]=i;
for (int j=0;p[j]*i<=n;j++){
st[p[j]*i]=1;
if(i%p[j]==0) break;
}
}
}
int main()
{
int n;
cin>>n;
init(n);
int r=cnt-1;
int ans=0;
for (int i=1;i<cnt;i++){
while (r>=1&&p[i]+p[r]>n) r--;
if(r<i) break;
ans+=(r-i+1);
}
if(n>=4)ans++;
cout<<ans;
}