Goldbach's Conjecture POJ - 2262 线性欧拉筛水题 哥德巴赫猜想
2024-08-26 05:08:39
题意 哥德巴赫猜想:任一大于2的数都可以分为两个质数之和
给一个n 分成两个质数之和
线行筛打表即可 可以拿一个数组当桶标记一下a[i] i这个数是不是素数 在线性筛后面加个装桶循环即可
#include<cstdio>
#include<cstring>
using namespace std;
bool Is_Primes[];
int Primes[];
int cnt;
void Prime(int n){
cnt=;
memset(Is_Primes,,sizeof(Is_Primes));
for(int i=;i<=n;i++){
if(!Is_Primes[i])
Primes[cnt++]=i;
for(int j=;j<cnt&&i*Primes[j]<=n;j++){
Is_Primes[Primes[j]*i]=;
if(i%Primes[j]==)break;
}
}
memset(Is_Primes,,sizeof(Is_Primes));
for(int i=;i<cnt;i++){
Is_Primes[Primes[i]]=;
} }
int main(){
int n;
Prime();
while(scanf("%d",&n)==&&n){
int temp=;
for(int i=;i<cnt&&Primes[i]<n;i++){
// printf("%d \n",i);
if(Is_Primes[n-Primes[i]]==){
printf("%d = %d + %d\n",n,Primes[i],n-Primes[i]);
break;
}
} }
return ;
}
最新文章
- Js ==和===的区别
- design包 TabLayout使用
- 浅谈sizeof
- en_windows_10_multiple_editions_version_1511_x64.iso
- 7-11使用UNION合并查询
- BZOJ3799 : 字符串重组
- Android WebView中那些不得不解决的坑~~
- MHA手动切换 原创2 (主参与复制)
- nopCommerce 3.3正式发布及新增功能改进
- foreach真的比for性能高吗
- 1.Google Chrome浏览器 控制台全解析
- ASP.NET Core 2.2 十九. Action参数的映射与模型绑定
- 浅谈C#语言中的各种数据类型,与数据类型之间的转换
- python之路--MySQL权限管理 数据备份还原
- Python匿名函数(lambda)
- 7、 jade 、 ejs、express集成模板
- debug调试命令
- Android动画-View动画
- One Person Game(zoj3593+扩展欧几里德)
- @CookieValue使用须知