poj 2262 筛法求素数(巧妙利用数组下标!)
2024-10-19 04:29:01
Goldbach's Conjecture
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 41582 | Accepted: 15923 |
Description
In 1742, Christian Goldbach, a German amateur mathematician, sent a letter to Leonhard Euler in which he made the following conjecture:
Every even number greater than 4 can be
written as the sum of two odd prime numbers.
For example:
8 = 3 + 5. Both 3 and 5 are odd prime numbers.
20 = 3 + 17 = 7 + 13.
42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23.
Today it is still unproven whether the conjecture is right. (Oh
wait, I have the proof of course, but it is too long to write it on the
margin of this page.)
Anyway, your task is now to verify Goldbach's conjecture for all even numbers less than a million.
Input
The input will contain one or more test cases.
Each test case consists of one even integer n with 6 <= n < 1000000.
Input will be terminated by a value of 0 for n.
Each test case consists of one even integer n with 6 <= n < 1000000.
Input will be terminated by a value of 0 for n.
Output
For
each test case, print one line of the form n = a + b, where a and b are
odd primes. Numbers and operators should be separated by exactly one
blank like in the sample output below. If there is more than one pair of
odd primes adding up to n, choose the pair where the difference b - a
is maximized. If there is no such pair, print a line saying "Goldbach's
conjecture is wrong."
each test case, print one line of the form n = a + b, where a and b are
odd primes. Numbers and operators should be separated by exactly one
blank like in the sample output below. If there is more than one pair of
odd primes adding up to n, choose the pair where the difference b - a
is maximized. If there is no such pair, print a line saying "Goldbach's
conjecture is wrong."
Sample Input
8
20
42
0
Sample Output
8 = 3 + 5
20 = 3 + 17
42 = 5 + 37
Source
心得:自己写的筛法时间复杂度是O(n^2),利用数组下标省去一个循环后变成了O(n);妙不可言!!!
#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define N 1000000
int n,a[N];
bool pr[N];
void pdd()
{
int i,j;
for(i=;i<;i++) a[i]=;
a[]=; a[]=;
for(i=;i<;i++)
{
if(a[i]==)
{
for(j=i*;j<;j+=i) a[j]=;
}
}
}
int main()
{
int num;
int i,flag;
pdd();
while(scanf("%d",&num)!=EOF&&num!=)
{
for(flag=,i=;i<num;i++)
{
if(a[i]==&&a[num-i]==)
{
printf("%d = %d + %d\n",num,i,num-i);
flag=;
break;
}
}
if(flag==)
printf("Goldbach's conjecture is wrong.\n");
}
return ;
}
最新文章
- BZOJ 4453: cys就是要拿英魂![后缀数组 ST表 单调栈类似物]
- web主题公园版权信息破解:script.js加密文件
- V8 data struct
- SQL SERVER代码生成器必备
- ssh搭建后的简化
- 监控linux服务器网卡流量
- CSS 居中大全【转】
- 绑定线程到特定CPU处理器
- MySQL - “Timeout error occurred trying to start MySQL Daemon”解决方法
- linux 定时执行shell
- memcached 内存管理 分析(转)
- Android,机器狗应用
- Spring Cloud 自定义ConfigServer
- 4层板的pcb创建
- python下用OpenCV的圆形检测
- 如何通过SpringBoot官方手册集成RabbitMQ
- 使用ML.NET实现白葡萄酒品质预测
- Kotlin 扩展
- Python常用模块time &; datetime &;random 模块
- Ubuntu16.04下通过tar.gz包安装MySQL5.5.52
热门文章
- 外观模式(Facde)【设计模式】
- 【网络爬虫入门01】应用Requests和BeautifulSoup联手打造的第一条网络爬虫
- H264协议(转)
- TCP之listen&;backlog
- python基础===输入必须为数字的检验的另一种方法
- (十七)vmware无法将网络更改为桥接状态
- 在Github里集成Readthedocs服务
- IIS配置PHP环境(快速最新版)(转载+自创)
- js前端数据加密插件
- django渲染模板时跟vue使用的{{ }}冲突解决方法