NO.1 哥德巴赫猜想

Time Limit:1000MS Memory Limit:65536K
Total Submit:229 Accepted:44

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.

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

8
20
42
0

Sample Output

8 = 3 + 5
20 = 3 + 17
42 = 5 + 37

N0.2 数素数

Time Limit:1000MS Memory Limit:65536K
Total Submit:850 Accepted:65

Description

素数是的只能被1和它本身整除的自然数。判断一个数是素数的方法是使用2到该数的平方根的素数除它，若有能整除的则该数不是素数。

Input

本题有多组数据，每组数据由两个正整数M,N组成。（0＜M＜N＜1000000）

Output

输出一个整数，表示介于M,N之间（包括M,N）的素数的数量。

Sample Input

5 10
1 3
6 8

Sample Output

2
2
1


注意效率，数值比较大,这个题目并不是有些人想像的那么简单


第三题:


The problem with Tom

Time Limit: 1000 MS Memory Limit: 65536 K
Total Submit: 1 Accepted: 0

Description

One day,Tom's teacher give him a problem,give a number N(1<=N<=1000),it can be writen as a sum of some of positive integer.As N=s1+s2+s3+….But si must be the power of 2.Then Tom has to tell how many ways are there can sum up the given N. Two sequences with the same numbers but different orders are consider as one. Tom is poor in math,so as his best friend,slove this problem for him.
Input

Input consists of multiple test cases. Eath case contain a number N which described as before.

Output

For eath number,output a number stand the number of different kinds of string.

Sample Input

2
5
Sample Output

2
4

[此贴子已经被作者于2007-4-21 10:48:54编辑过]

[此贴子已经被作者于2007-4-20 16:15:22编辑过]

不知道素数本身算不算...

[此贴子已经被作者于2007-4-20 12:23:03编辑过]

#include <math.h>
#include <stdio.h>
int prime (int n)
{
int i,temp;
temp=sqrt(n);
for (i=2;i<=temp;i++)
if (n%i==0) return 0;
return 1;
}

int main()
{int num,i;
int a[20]={2,3,5,7,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73};
scanf("%d",&num);
for(i=0;i<20;i++)
if(prime(num-a[i]))
{
printf("%d = %d + %d\n",num,a[i],num-a[i]);
getch();
return 0;
}
printf("error!");
getch();
return 0;
}

a数组好象考虑多了...

大家看看~``很少做这些题,,不怕丢脸

[此贴子已经被作者于2007-4-20 12:37:38编辑过]

没事写了一个 请高手指正 thx

//***************************************************************
// Goldbach.c -- Goldbach's conjecture
// Author: Javal
// Date: 2007/04/20
//****************************************************************
#include<stdio.h>
#include<math.h>

#define SIZE 100
#define TRUE 1
#define FALSE 0
#define LOWER 6
#define UPPER 1000000

typedef int status;

status isOddPrime(int num);
status isEven(int num);
void getInput(void);
void parseNum(void);
void showResult(void);

static int iArr[SIZE][3];
static int input = 0;
static int index = 0;
status flag = TRUE;

int main(void)
{
getInput();
parseNum();
showResult();

return 0;
}

status isEven(int num)
{
return (num%2 ? 0 : 1);
}

void getInput(void)
{
printf("Please enter a series of even integers(enter 0 to terminate):\n");

scanf("%d", &input);
fflush(stdin);
while (index < SIZE)
{
if (input == 0)
{
iArr[index++][0] = input;
break;
}
if (isEven(input) && input >= LOWER && input <= UPPER)
{
iArr[index++][0] = input;
}
else
{
printf("Invalid data! Please try again!\n");
}
scanf("%d", &input);
fflush(stdin);
}
}

void parseNum(void)
{
int i = 0;

for (index = 0; iArr[index][0] != 0; ++index)
{
if (! flag)
{
printf("Goldbach's conjecture is wrong.\n");
}

for(i = 3; i <= iArr[index][0]/2; ++i)
{
flag = FALSE;
if (isOddPrime(i) && isOddPrime(iArr[index][0] - i))
{
iArr[index][1] = i;
iArr[index][2] = iArr[index][0] - i;
flag = TRUE;
break;
}
}
}
}

status isOddPrime(int num)
{
int i = 0;

for (i = 2; i <= sqrt(num); ++i)
{
if (num % i == 0)
{
return FALSE;
}
}

return TRUE;
}

void showResult(void)
{
printf("According to Goldbach's conjecture, the result is:\n");

for(index = 0; iArr[index][0] != 0; ++index)
{
printf("%d = %d + %d\n", iArr[index][0], iArr[index][1], iArr[index][2]);
}
}

[此贴子已经被作者于2007-4-20 13:40:42编辑过]

回来晚了,发题目都没有通知我一下.要不我就逃课了
歌德猜想:
#include<stdio.h>
int a[168]={2,3,5,7,11,13,17,19,23,29,
31,37,41,43,47,53,59,61,67,
71,73,79,83,89,97,101,103,107,
109,113,127,131,137,139,149,151,
157,163,167,173,179,181,191,193,
197,199,211,223,227,229,233,239,
241,251,257,263,269,271,277,281,
283,293,307,311,313,317,331,337,
347,349,353,359,367,373,379,383,
389,397,401,409,419,421,431,433,
439,443,449,457,461,463,467,479,
487,491,499,503,509,521,523,541,
547,557,563,569,571,577,587,593,
599,601,607,613,617,619,631,641,
643,647,653,659,661,673,677,683,
691,701,709,719,727,733,739,743,
751,757,761,769,773,787,797,809,
811,821,823,827,829,839,853,857,
859,863,877,881,883,887,907,911,
919,929,937,941,947,953,967,971,
977,983,991,997};
int prime(int n)
{
int i;
if(n==1)return 0;
else
{
for(i=0;a[i]*a[i]<=n&&i<168;i++)
{
if(n%a[i]==0)
return 0;
}
return 1;
}
}
void main()
{
long n,i;
while(scanf("%ld",&n)!=EOF)
{
if(n==0)
break;
else
{
for(i=3;i<=n/2;i++)
{
if(prime(i))
{
if(prime(n-i))
{
printf("%ld=%ld+%ld\n",n,i,n-i);
break;
}
}
}
}
}
}

第二个题目我也做过了,就留给大家做吧

[此贴子已经被作者于2007-4-20 12:51:14编辑过]