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编辑过]

不要那么小看第二题，我特别在下面写了个注意，要特别注意效率

这几天比较忙,所以没有及时回复,抱歉

基本上都没有问题.

I喜欢C版主的的确如11楼所说少了点.
16楼效率故然很高,但所占的空间似乎太大,大家再想想看能不能找到一种能够达到题目的效率又不会使用这么大的空间的算法

另外题目好像出的比较简单,在加一个给大家热热身

大家不要觉得自己英语不好,大家本来英语都不好,都是自己积累的,我四级都没过,现在用英文的操作系统,做英文题目,不懂就去查,多用几次就记住了,其实学电脑可以学到很多英语的东西,大家不防试试,比那些整天拿着一本厚厚的字典背单词强多了,英语是一个积累的过程,有不懂的就问,给大家一个在线词典的网站
http://www.iciba.com/

遇到不懂的英语单词到这去查一般都有解释,如果还是不懂意思,就到论坛上来问

的确很快,我有一个递归也准备改成FOR,看一下运行效率怎么样.

第一题:

#include<stdio.h>
#include<math.h>
int a[168]={2};

void init(void) //储存1000内的素数
{
int i,j,k=1,sure=1;
for(j=3;j<1000;j++)
{
for(i=2;i<=sqrt(j);i++)
if(j%i==0)
{
sure=0;
break;
}
if(sure)
a[k++]=j;
sure=1;
}
}

int prime(long n) //判断是否为素数
{
int i;
if(n<2)
return 0;
if(n==2)
return 1;
for(i=0;i<168;i++)
{
if(a[i]>sqrt(n))
break;
if(n%a[i]==0)
return 0;
}
return 1;
}

int main(void)
{
long n,i;
init();
while(scanf("%ld",&n))
{
for(i=3;;i++)
if(prime(i))
if(prime(n-i))
{ printf("%ld=%d+%ld\n",n,i,n-i);
break;
}
}
return 0;
}

第三题(只适合2N以内的数)

#include <stdio.h>
#define N 501 为了算更大的数,将N定义得更大点,不过空间方面就浪费了

int a[N]={0};
void init(void) //初始化先算出1000以内的数的种数,存储在数组中
{
int i;
for(i=0;i<N;i++)
{
if(i==0)
a[i]=1;
else
if(i==1)
a[i]=2;
else
a[i]=a[i-1]+a[i/2];
}

}

int main(void)
{
int n;
init();
while(scanf("%d",&n))
printf("%d\n",a[n/2]); //2N与2N+1是一样的.
return 0;
}

第二题我还在找一种使得空间和时间方面最佳的情况,暂不发上来

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

第二个实在没法优化了,以后再想想,勉强可以达到题目的要求,1000000以内的数可以在1秒之内算出

#include<stdio.h>
#include<math.h>
#include<time.h>

int a[168]={2};

void init(void) //求出1000以内的所有素数,储存在数组中
{
int i,j,k=1,sure=1;
for(j=3;j<1000;j++)
{
for(i=2;i<=sqrt(j);i++)
if(j%i==0)
{
sure=0;
break;
}
if(sure)
a[k++]=j;
sure=1;
}
/* for(i=0;i<168;i++) //输出1000以内的素数
printf("%5d",a[i]);
*/
}

int prime(long n) //判断该数是否为素数
{
int i;
if(n<2)
return 0;
if(n==2)
return 1;
for(i=0;i<168;i++)
{
if(a[i]>sqrt(n))
break;
if(n%a[i]==0)
return 0;
}
return 1;
}

int main(void)
{
long m,n,i;
clock_t start,over; // 定义两个变量用来储存时间
int sum;

while(scanf("%ld%ld",&m,&n))
{
start=clock(); //记录起始时间
init();
sum=1;
if(m%2==0)
{
if(prime(m))
sum++;
i=m+1;
}
else
i=m;
for(;i<=n;i+=2)
if(prime(i))
sum++;
printf("%d\n",sum);
over=clock(); //记录结束时间
printf("消耗时间:%lfms\n",(double)(over-start)); //输出程序运行时间
}
return 0;
}

[此贴子已经被作者于2007-4-22 11:22:45编辑过]

# include<stdio.h>
# include<math.h>
int fun(int m)
{
int i,n,flag;
n=sqrt(m);
if(m==1 || m==3)
flag=1;
else(m==2) //是不是有点问题
flag=0;
else
{
for(i=2;i<=n;i++)
{
if(m%i==0)
break;
}
if((i-1)==n)
flag=1;
else
flag=0;
}
return(flag);
}
void main()
{
int m,n,i,flag,temp,x=0;
printf("please input m && n:");
scanf("%d%d",&m,&n);
if(m>n)
{
temp=m;m=n;n=temp;
}
for(i=m;i<=n;i++)
{
flag=fun(i);
if(flag)
x++;
}
printf("have %d data.\n",x);
}

[此贴子已经被作者于2007-9-2 21:08:04编辑过]