求助一到素数题/uva,543

问题描述

求助一到素数题/uva,543

Problem A : Goldbach's Conjecture
From: UVA, 543Submit

Time Limit: 3000 MS
In 1742, Christian Goldbach, a German amateur mathematician, sent a letter to Leonhard Euler in which he made the following conjecture:
Every number greater than 2 can be written as the sum of three prime numbers.
Goldbach cwas considering 1 as a primer number, a convention that is no longer followed. Later on, Euler re-expressed the conjecture as:
Every even number greater than or equal to 4 can be expressed as the sum of two 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 as expressed by Euler for all even numbers less than a million.

Input The input file will contain one or more test cases.
Each test case consists of one even integer n with .
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."

Sample Input

820420
Sample Output

8 = 3 + 520 = 3 + 1742 = 5 + 37

Miguel A. Revilla
1999-01-11
新手写代码:
#include
#include
#include
#define N 1000
using namespace std;
int main()
{
int a[N];
int n;
memset(a,0,sizeof(a));
int flag1=0,k=1;
a[0]=3;
for(int i=5;i<N;i++)
{
for(int j=2;j*j<=i;j++)
{
if(i%j==0)
{
flag1=1;
break;
}
}
if(!flag1)
{
a[k++]=i;
}
flag1=0;
}
while((scanf("%d",&n))!=EOF&&(n!=0))
{
int flag2=0;
for(int i=0;a[i]<=n;i++)
{
for(int j=i+1;j<=k;j++)
{
if((n-a[i])==a[j])
{
flag2=1;
printf("%d = %d + %dn",n,a[i],a[j]);
break;
}
}
if(flag2)
break;
}
if(!flag2)
printf("Goldbach's conjecture is wrong.");
}
return 0;
}

解决方案

你的算法不能改了,没办法实现,因为你的算法是先获得一个全是素数的数组,976696 = 53 + 976643,这种test case已经溢出了

解决方案二:

这是我ac的代码,上面说错了,你的可以试试看把数组换成list,说不定也可以,不能说没办法实现

 #include <iostream>
using namespace std;
bool isPrime(int m){
    for(int i=2;i*i<=m;i++){
        if(m%i==0){
            return false;
        }
    }
    return true;
}
int main(){
    int n;
    cin>>n;
    while(n!=0){
        bool flag=false;
        for(int i=3;i<=n/2;i++){
            if(isPrime(i)){
                if(isPrime(n-i)){
                    cout<<n<<" = "<<i<<" + "<<n-i<<endl;
                    flag=true;
                    break;
                }
            }
        }
        if(!flag){
            cout<<"Goldbach's conjecture is wrong."<<endl;
        }
        cin>>n;
    }
}
时间: 2024-10-29 04:28:32

求助一到素数题/uva,543的相关文章

c#代码-求助一道c语言题啊,很急啊

问题描述 求助一道c语言题啊,很急啊 众所周知,琪露诺(チルノ,Cirno)是幻想郷 (げんそうきょう)中首屈一指的天才,可以说⑨就是她的代名词. 然而如今,她遇到了一个和⑨有关的难题.你能帮助她么? 题目是这样的,给出两个数 a 和 b (0 <= a <= b <= 10^10000),求 a 到 b 之间(包括a和b)的数字中,有多少个数字是包含9的(例如 19,910 等都是包含9的数字). 输入 第一行为一个数字 T (0 < T <= 100) 表示数据组数. 之

UVa 543 Goldbach&#039;s Conjecture:素数&amp;amp;哥德巴赫猜想

543 - Goldbach's Conjecture Time limit: 3.000 seconds http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=484 In 1742, Christian Goldbach, a German amateur mathematician, sent a letter

UVa 10099:The Tourist Guide(Floyd, 最大生成树)

链接: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1040 题目: Problem D The Tourist Guide Input: standard input Output: standard output Mr. G. works as a tourist guide. His current

uva 193 - Graph Coloring

点击打开链接 题目意思:  给定n个节点,节点的编号为1-n,在给定m个节点链接的信息,现在要求对节点图色,只有两种颜色可以黑色和白色并且相邻的节点不能同时为黑色但是可以为白色,要求黑色节点最多的个数,以及一组节点的编号 解题思路:  对于节点而言,每一个节点就是两种情况,白色或黑色,那么我们知道这一个解空间树的每一层就是一个节点,那么我们只要去搜索这个解空间就可以了,这一题的数据虽然n到达100,但是真正的数据没那么大,不会超时. 注意事项:   这一题uva最后没有换行 , poj有换行,注

最短路专题【完结】

第一题 hdu 1317 XYZZY 点击打开hdu 1317 思路: 1 题目的图是一个有向图,并且可能存在环.第一个点的能量值为100,边的权值利用能量大小,例如2点为-60,如果1->2那么value[1][2] = -602 题目明确指出如果是要win的话,那么必须是经过的每条边都要大于0.那么我们只要把那些经过松弛操作后的点大于0的入队即可,小于等于0的点肯定不会出现在最终的路径上.3 如果存在正环的话,那么就有能量值无限大,那么这个时候只要判断这个点能否到达n4 判断是否是有环还是五

矩阵快速幂专题【完结】

第一题 hdu 1757 A Simple Math Problem 点击打开链接 思路:矩阵快速幂 分析: 1 最简单的矩阵快速幂的题目,直接利用矩阵求解即可 点击打开查看代码 第二题 hdu 1575 Tr A 点击打开hdu 1575 思路: 矩阵快速幂 分析: 1 题目给定一个n*n的矩阵要求矩阵的k次幂之后的矩阵的对角线的和 2 矩阵快速幂的裸题 点击打开查看代码 第三题 hdu 2604 Queuing 点击打开hdu 2604 思路: 递推+矩阵快速幂 分析; 1 根据题目的意思,

并查集专题【完结】

个人整理 并查集 [poj] 第一题 poj 1182 食物链 点击打开链接poj 1182 思路: 带权并查集 分析: 1 典型的带权并查集的题目 2 如果x和y是同类的关系认为是0,如果是x吃y那么关系认为是1,那么x和y的关系为2就说明y吃x 3 那么如果x和y同类则rank[x] == rank[y] , 如果x吃y那么rank[x] == (rank[y]+1)%3 , 注意mod3的使用 点击查看代码 第二题 poj 1308 Is It A Tree? 点击打开链接 poj 130

最小生成树【完结】

第一题 hdu 1232 畅通工程 点击打开hdu 1232 思路:模板题 点击查看代码 第二题 hdu 1233 还是畅通工程 点击打开hdu 1233 思路:模板题 点击查看代码 第三题 uva 10034 Freckles 点击打开uva 10034 思路:模板题 点击查看代码 第四题 uva 10397 Connect the Campus 点击打开uva 10397 思路:模板题 点击查看代码 第五题 uva 10369 Arctic Network 点击打开uva 10369 思路:

UVa 11198:Dancing Digits,Rujia Liu的神题

题目链接: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2139 类型: 隐式图搜索,  BFS, 哈希判重,模拟 原题: Digits like to dance. One day, 1, 2, 3, 4, 5, 6, 7 and 8 stand in a line to have a wonderful