当前位置:网站首页>2020.11.22考试哥德巴赫猜想题解
2020.11.22考试哥德巴赫猜想题解
2022-08-10 01:55:00 【bj_hacker】
题目
哥德巴赫猜想
【问题描述】
哥德巴赫猜想:任何大于 4 的整数都可以拆成两个奇质数的和。
比如:8=3+5.
20=3+17=7+13
42=5+37=11+31=13+29=19+23
你的任务是:验证小于 1000 000 的数满足哥德巴赫猜想。
【输入】
输入包含多组测试数据,每组测试数据一个 n(6<=n<1000 000)。
读入以 0 结束。
【输出】
对于每组数据,输出形如 n=a+b,其中 a,b 是奇质数。若有多组满足条件的 a,b,输
出 b-a 最大的一组。若无解,输出“Goldbach’s conjecture is wrong。
思路
艾氏筛法+循环判断另一数
代码实现
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
int n;
bool as[maxn];
inline void init(){
as[1]=true;
for(int i=2;i<=1000000;i++){
if(as[i])continue;
for(int j=2*i;j<=1000000;j+=i)as[j]=true;
}
}
int main(){
init();
while(1){
scanf("%d",&n);
if(!n)break;
if(n%2==1){
printf("Goldbach’s conjecture is wrong\n");
continue;
}
printf("%d = ",n);
for(int i=3;i<=n;i++){
if(as[i])continue;
if(!as[n-i]){
printf("%d + %d\n",i,n-i);
break;
}
}
}
return 0;
}
边栏推荐
猜你喜欢
随机推荐
桌面云组件介绍与安装
【wpf】拖拽的简单实现
你有对象类,我有结构体,Go lang1.18入门精炼教程,由白丁入鸿儒,go lang结构体(struct)的使用EP06
中文NER的SOTA:RICON
按钮倒计时提醒
Open3D 网格均匀采样
【QT】QT项目:自制Wireshark
【论文笔记】基于深度学习的机器人抓取虚拟仿真实验教学系统
Database management tool: dynamic read-write separation
Algorithm and voice dialogue direction interview question bank
Under pressure, there must be cowards
web开发概述
C# 单例模式
手把手教你搭建ELK-新手必看-第一章:什么是ELK?
在蓝图中给组件动态加子Actor组件
OpenCV图像处理学习三,Mat对象构造函数与常用方法
《GB39732-2020》PDF下载
首次在我们的centos登录我们的Mysql
【干货】集成学习原理总结
牛客刷题——剑指offer(第四期)