nefu2哥德巴赫猜想 素数筛

这个题是我去年一开始就看了的,当时想了一下午没有结果,发现AC率太低也就释然了==也难怪,怎么可能一开始就会素数筛(⊙﹏⊙)b这个题还是照着模板改了好久的呢

1)0,1分不清   2)int内存超了用布尔

<center>

猜想

</center>

Problem : 2

Time Limit : 3000ms

Memory Limit : 65536K

description

哥德巴赫(Goldbach ]C.,1690.3.18~1764.11.20)是德国数学家;出生于格奥尼格斯别尔格(现名加里宁城);曾在英国牛津大学学习;原学法学,由于在欧洲各国访问期间结识了贝努利家族,所以对数学研究产生了兴趣;曾担任中学教师。1725年,到了俄国,同年被选为彼得堡科学院院士;1725年~1740年担任彼得堡科学院会议秘书;1742年,移居莫斯科,并在俄国外交部任职。
1742年,哥德巴赫在教学中发现,每个不小于6的偶数都是两个素数(只能被1和它本身整除的数)之和。如6=3+3,14=3+11等等。公元1742年6月7日哥德巴赫写信给当时的大数学家欧拉,欧拉在6月30日给他的回信中说,他相信这个猜想是正确的,但他不能证明。叙述如此简单的问题,连欧拉这样首屈一指的数学家都不能证明,这个猜想便引起了许多数学家的注意。从哥德巴赫提出这个猜想至今,许多数学家都不断努力想攻克它,但都没有成功。
我们不需要你去证明哥德巴赫猜想。
如果哥德巴赫猜想是正确的,一个(不小于6的)偶数,都是两个素数之和。那么这个偶数能被至少一个素数对表示,如14,即可以表示为14=3+11,也可以表示为14=7+7。不同的偶数对应的素数对的数目是不一样的,如偶数6,就只能表示为6=3+3。对于每个给定的偶数,我们希望知道有多少素数对的和等于该偶数。

input

有多组测试数据。每组测试数据占一行,包含唯一的一个正偶数n.(6 <= n <= 2^24,)。 输出以EOF结束。

output

对于每个输入的偶数,输出一行包含唯一的一个整数:表示有多少个素数对的和是输入的偶数。

sample_input

6
14

sample_output

1
2
#include <iostream>
#include<cstdio>
#include<cstring>
#define N 17000000
using namespace std;
bool isnotprime[N];//0说明不是素数 1是素数
long prime[N];
long n,q;
int main()
{
    q=0;
    memset(isnotprime,0,sizeof(isnotprime));
    isnotprime[0]=1;isnotprime[1]=1;isnotprime[2]=0;
    for(long i=2;i<N;i++)
    {
         if(!isnotprime[i])
         {
              prime[q]=i;q++;
         }
         for(long j=0;j<q&&prime[j]*i<N;j++)
         {
              isnotprime[prime[j]*i]=1;
              if(!(i%prime[j])) break;
         }
    }
    //for(long i=0;i<300;i++) cout<<prime[i]<<' ';
    while(~scanf("%ld",&n))
    {
         int num=0;
         for(long i=0;prime[i]<=n/2;i++)
         {
              if(!isnotprime[n-prime[i]])
              num++;
         }
         printf("%d\n",num);
    }
    return 0;
}


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

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-30 15:34
广州大学_2023
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 会员标识 头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议