ural 1356. Something Easier(数论,哥德巴赫猜想)
2024-08-21 10:42:05
1356. Something Easier
Time limit: 1.0 second
Memory limit: 64 MB
Memory limit: 64 MB
“How do physicists define prime numbers? Very easily: prime numbers are the number 2 and all the odd numbers greater than 2. They may show that this definition corresponds to the mathematical one: 3 is prime, 5 is prime, 7 is prime… 9? 9 is certainly not prime. Then: 11 is prime, 13 is prime. So 9 is the experiment mistake.”
From mathematical analysis course
Once physicist and mathematician argued how many prime numbers one needed for the purpose that their sum was equal to N. One said that it wasn’t known and the other that 3 was always enough. The question is how many.
Input
The first line contains T, an amount of tests. Then T lines with integer N follow (0 ≤ T ≤ 20; 2 ≤ N ≤ 109).
Output
For each test in a separate line you should output prime numbers so that their sum equals to N. An amount of such prime numbers is to be minimal possible.
Sample
input | output |
---|---|
7 |
2 |
题意
一位物理学家和一位数学家正在争论最少几个质数的和为N。
其中一个说这无从知晓,另一个说3个就够了。
input
第一行包含一个整数T,表示测试点数量。
接下来T行,每行一个整数N。
(0<=T<=20,2<=N<=10^9)
output
输出一些质数,使它们的和为N,质数的个数要尽量少。
思路:根据哥德巴赫猜想,
任一大于2的偶数都可写成两个质数之和。
任一大于7的奇数都可写成三个素数之和。
详细内容可参照维基百科http://zh.wikipedia.org/wiki/%E5%93%A5%E5%BE%B7%E5%B7%B4%E8%B5%AB%E7%8C%9C%E6%83%B3。
#include <iostream>
#include <sstream>
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <list>
#include <map>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <set>
#include <deque>
#include <bitset>
#include <functional>
#include <utility>
#include <iomanip>
#include <cctype>
using namespace std; #define FOR(i,a,b) for(i = (a); i < (b); ++i)
#define FORE(i,a,b) for(i = (a); i <= (b); ++i)
#define FORD(i,a,b) for(i = (a); i > (b); --i)
#define FORDE(i,a,b) for(i = (a); i >= (b); --i)
#define max(a,b) ((a) > (b)) ? (a) : (b)
#define min(a,b) ((a) < (b)) ? (a) : (b)
#define CLR(a,b) memset(a,b,sizeof(a))
#define PB(x) push_back(x) typedef long long LL;
typedef vector<int> VI; const int MAXN = ;
const int hash_size = ;
const int INF = 0x7f7f7f7f; bool p[MAXN]={}, flag;
int prime[MAXN]={}, q[], n, d;
void init()
{
int i;
for(i = ; i <= ; i++)
if(!p[i])
{
prime[]+=;
prime[prime[]]=i;
for(int j=i+i;j<=;j+=i)
p[j]=true;
}
} bool isprime(int n){//判断n是否是一个质数
if (n == )
return true;
else {
int sq, i;
sq = int(sqrt(n*1.0));
for (i = ; i <= sq+; ++i)
if (n%i == )
return false;
return true;
}
} void dfs(int k,int x,int y)
{//将奇数进行分解
int i;
if (flag) return;
if (k == )
{
if (isprime(x))
{
FORD(i, d, )
printf("%d ", prime[q[i]]);//进行输出
printf("%d\n", x);
flag = true;//找到了一个分解
}
return;
}
for (i = y; i<=prime[]; ++i)
{
if (prime[i]*k > x) return;
q[k] = i;
dfs(k-, x-prime[i], i);
}
} int main()
{
init();
int t, i;
scanf("%d", &t);
while (t--) {
scanf("%d", &n);
if (isprime(n))
printf("%d\n", n);
else if (n&) {
d = ;
flag = false;
while (!flag)
dfs(++d, n, );//先分2分,再分3个
}
else {
int tmp;
FORE(i, , prime[]) {
tmp = n - prime[i];
if (isprime(tmp)) {
printf("%d %d\n", prime[i], tmp);
break;
}
}
}
}
return ;
}
最新文章
- pptpvpn 连接后 无法上外网
- 《Qt Quick 4小时入门》学习笔记4
- MFC 单文档消息执行顺序。
- 操作系统开发系列—13.i.进程调度 ●
- Arduino可穿戴开发入门教程(大学霸内部资料)
- ORM框架-VB/C#.Net实体代码生成工具(EntitysCodeGenerate)【ECG】4.5
- Ubuntu 设定壁纸自动切换的shell脚本
- 浅谈reverse_iterator的base()函数
- BrnShop开源网上商城第三讲:插件的工作机制
- JavaScript------处理Json数据
- js中的数组对象排序(方法sort()详细介绍)
- A Walk Through the Forest
- IntelliJ IDEA 17和Maven构建javaWeb项目
- python学习笔记4_类和更抽象
- java工程师的成长历程
- Spring MVC 注解
- 关于electron的跨域问题,有本地的图片的地址,访问不了本地的图片
- 【Spring环境搭建】在Myeclipse下搭建Spring环境-web开发
- eShopOnContainer 第一步
- python 缺失值处理(Imputation)