POJ 2262 Goldbach's Conjectureゴシックバッハ予想

http://poj.org/problem?id=2262
Goldbach's Conject ure
Time Limit: 1000 MS
 
メモリLimit: 65536 K
Total Submissions: 33301
 
Acceepted: 12788
Description
In 1742、Christian Goldbach、a German mateur mathematiian、sent a letter to Leonhard Euler in which he made the follwing conjece： 
Every even number greater than 4 can be 
written as the sum of two odd preme numbers.
For example: 
8=3+5.Both 3 and 5 arodd preme numbers. 
20=3+17=7+13. 
42=5+37=11+31=13+29=19+23.
Today it is still unproven whethe r the conjecure is right.（Oh wait，I have the proof course，but it is too long to write it on the maring of this page.） 
Anyway、your task is now to verify Goldbach's conjecure for all even numbers less than a milion. 
Input
The input will contain one or more test cases. 
Each test case consists of one even integer n with 6<=n<100000. 
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 ard prininmes.Numbers and operaors shors shaparated byexactlyone blank like the sampputupputbelow.If there is is more thethethethethetherererereisismorimomothethethethethethethethethethethethetheeeeeeedededededededededededededededededededepapapapapapapapapapapapapapapapapapapapapapapapapapapapapapapapapapapapapapapapapaparated eeeパir、print a line saying「Goldbach's conjecure is wrong.」
Sample Input

8
20
42
0

Sample Output

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

論題を数える。主に一つの数が素数かどうかを判断します。コードは以下の通りです。

#include"stdio.h"
int a[1000002];
int b[41540];
int main()
{
	int N;
	int i,j;
	for(i=2;i<1002;i++)
	{
		if(!a[i])
		{
			for(j=i*i;j<1000002;j+=i)
				a[j]=1;
		}
	}
	b[0]=2;
	for(j=1,i=3;i<500002;i+=2)
	{
		if(!a[i])
		{
			b[j++]=i;
		}
	}
	while(scanf("%d",&N)!=EOF && N)
	{
	
		for(i=0;b[i]<N;i++)
			if(!a[N-b[i]])
				break;
		printf("%d = %d + %d
",N,b[i],N-b[i]);
		
	}
	return 0;
}

イinjili
2262
Acceepted
4244 K
141 MS
C++
427 B
          
               時間141 MS、少し遅くなりました。コードの改善を試みました。

#include"stdio.h"
int a[1000002];
int main()
{
	int N;
	int i,j;
	for(i=2;i<1002;i++)
	{
		if(!a[i])
		{
			for(j=i*i;j<1000002;j+=i)
				a[j]=1;
		}
	}
	while(scanf("%d",&N)!=EOF && N)
	{
	
		for(i=2;i<N;i++)
			if(!a[i] && !a[N-i])
				break;
		printf("%d = %d + %d
",N,i,N-i);
		
	}
	return 0;
}

2262
Acceepted
4076 K
125 MS
C++
325 B
              125 MSの時間がかかりますか？それとも少し遅いですか？コードの改善を試みます。

#include"stdio.h"
char a[1000002];
int main()
{
	int N;
	int i,j,t;
	for(i=0x03;i<0x3ea;i+=0x02)
	{
		if(!a[i])
		{
			for(j=i*i;j<0xf4242;j+=i)
				a[j]=0x01;
		}
	}
	while(scanf("%d",&N)!=EOF && N)
	{
		t=N/2;
		for(i=0x03;i<=t;i+=0x02)
			if(!a[i] && !a[N-i])
				break;
		printf("%d = %d + %d
",N,i,N-i);
		
	}
	return 0;
}

イinjili
2262
Acceepted
1140 K
94 MS
C++
354 B
     
71
11749546(3)
イinjili
1140 K
94 MS
C++
354 B
 消耗時間94 MS。C++の中で71位です。
                        コードの改善を試み、ACだけでなく性能を向上させます。