Goldbach`s Conjecture

题意:
给出一个,求有多少对素数相加等于

思路:
打个素数表就很简单了,注意一个细节,数组一个字节,可以开四个字节,在这题如果开会超内存,而且以内只有个素数。

MyCode:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e7+7,maxm=1e6+7;
bool vis[maxn];
inline ll read() {
    ll s = 0, w = 1;
    char ch = getchar();
    while (ch < 48 || ch > 57) {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (ch >= 48 && ch <= 57)
        s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
int prime[maxm];
int sieve(int n=1e7) {
    for(int i=2;i*i<=n;++i)
        if(!vis[i])
            for(int j=i*i;j<=n;j+=i) vis[j]=true;
    int k=0;
    for(int i=2;i<=n;++i)    if(!vis[i])
        prime[++k]=i;
    return k;
}
//664579
int main() {
    int n,ans=0,cas=0,k=sieve(),t=read();
    while(t--) {
        n=read();
        ans=0;
        for(int i=1;i<=k;++i) {
            if(prime[i]>(n>>1)) break;
            if(!vis[n-prime[i]]) ++ans;
        }
        printf("Case %d: %d\n",++cas,ans);
    }
    return 0;
}

kuangbin带我飞

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
2 收藏 评论
分享

全站热榜

正在热议