686 - Goldbach's Conjecture (II)

[little joey]

Sorry, it was a typo

For 543 (I guess that's what you mean) I don't think it's important if you have the same prime listed twice.

[WR]

Hi, could anybody please confirm or reject the following results
for problem 686?

input ---> output

22292 ---> 177
30000 ---> 602
32000 ---> 312
100 ---> 6
20 ---> 2
32760 ---> 856
32766 ---> 517

My program is very similar to that for problem 543, but I'm getting
WA for this one.

Maybe somebody has any suggestions?!

[Dominik Michniewski]

Last two lines of your outputs are wrong. My solution outputs :
32760 => 857
32766 => 518

Best regards
DM

[WR]

Thanks a lot, DM

haven't found the mistake yet but certainly will.


added:

Silly mistake sure enough (just forgot a prime);
program's not too fast but accepted.

Thanks again

[eshika]

I have checked the code several times but cannot find out the error. Could anybody suggest?

Code: Select all

//deleted

[Antonio Ocampo]

Hi eshika

Try this

Input:
4

Output
1

Hope it helps

[eshika]

Thanks a lot!

[pipo]

greetings...

i sovled 686 problem.. but i got WA...

the solution is very simple...

first.. precalculate 65536 prime numbers..

and then, input a value of sum..

if i is a prime number and sum-i is a prime number, increase counter..

so that print the counter..

and i have tested some inputs.. in my thought the resut is right..

why i got WA ?

my code is...

Code: Select all

#include <stdio.h>

#define MAX		65536

#define TRUE	1
#define FALSE	0

void main(void)
{
	char prime[MAX];
	int i, j;
	int half_value;
	int sum;
	int cnt;
	
	prime[0] = FALSE;
	prime[1] = FALSE;

	for ( i = 2 ; i < MAX ; i++ ) 
	{
		if ( prime[i] == FALSE )
			continue;

		j = i + i;

		while ( j < MAX )
		{
			prime[j] = FALSE;

			j += i;
		}
	}

	while ( 1 ) 
	{
		scanf("%d", &sum);

		if ( sum == 0 ) 
			break;

		cnt = 0;
		half_value = sum / 2;

		for ( i = 2 ; i <= half_value ; i++ ) 
			if ( prime[i] && prime[sum-i]) 
					cnt++;

		printf("%d\n", cnt);
	}	
}

[emotional blind]

your prime number list generation is wrong
you have to include the loop

Code: Select all

for(i=0;i<MAX;i++)prime[i]=TRUE;

before

Code: Select all

prime[0] = FALSE; 
   prime[1] = FALSE; 

[pipo]

thanks a lot .. emotional blind...

thanks to you, i got AC...

[Sedefcho]

For anyone who may need some sample I/O

INPUT

Code: Select all

4
6
12
10
14
16
100
1000
1002
10000
22292
32306
32502
32760
32766
0

OUTPUT

Code: Select all

1
1
1
2
2
2
6
28
36
127
177
251
491
857
518

[tmdrbs6584]

#include<iostream.h>
#include<math.h>
int main(){
int n;
while(cin >> n){
if(n==0) break;
int a[20000]={2,0,},i,j,cnt=1,ccnt=0,cc[20000]={0,},ccc[20000]={0,};
for(i=3;i<n;i++){
int sw=0;
for(j=2;j<=sqrt(i);j++)
if(i%j==0) sw=1;
if(sw==0){
a[cnt]=i;
cnt++;
}
}
for(i=0;i<cnt;i++){
for(j=0;j<cnt;j++){
if(a+a[j]==n){
cc[ccnt]=a;
ccc[ccnt]=a[j];
ccnt++;
}
}
}
cnt=0;
for(i=0;i<ccnt;i++){
for(j=0;j<ccnt;j++){
if(i!=j)
if(cc==ccc[j] && ccc==cc[j]){cc=0; ccc=0;}
}
}
for(i=0;i<ccnt;i++)
if(cc!=0) cnt++;
cout << cnt << endl;
}
return 0;
}

[tmdrbs6584]

This is my source, but why TLE??
#include<iostream.h>
#include<math.h>
int main(){
int n;
while(cin >> n){
if(n==0) break;
int a[20000]={2,0,},i,j,cnt=1,ccnt=0,cc[20000]={0,},ccc[20000]={0,};
for(i=3;i<n;i++){
int sw=0;
for(j=2;j<=sqrt(i);j++)
if(i%j==0) sw=1;
if(sw==0){
a[cnt]=i;
cnt++;
}
}
for(i=0;i<cnt;i++){
for(j=0;j<cnt;j++){
if(a+a[j]==n){
cc[ccnt]=a;
ccc[ccnt]=a[j];
ccnt++;
}
}
}
cnt=0;
for(i=0;i<ccnt;i++){
for(j=0;j<ccnt;j++){
if(i!=j)
if(cc==ccc[j] && ccc==cc[j]){cc=0; ccc=0;}
}
}
for(i=0;i<ccnt;i++)
if(cc!=0) cnt++;
cout << cnt << endl;
}
return 0;
}
And Here is my test data,
INPUT:
1 2 3 4 5 6 7 8 9 10 20 30 40 50 60 70 80 90 100 200 300 400 500 600
700 800 900 1000 2000 3000 4000 5000 6000 7000 8000 9000 10000
20000 30000
OUTPUT:
0 0 0 1 1 1 1 1 1 2 2 3 3 4 6 5 4 9 6 8 21 14 13 32 24 21 48 28 37 104 65
76 178 119 106 242 127 231 602

Why TLE??

[tmdrbs6584]

Oh, I got AC,,
I changed my code
if(i%j==0) sw=1;
to
if(i%j==0){sw=1; break;}
Thanks

[tmdrbs6584]

Oh, I got AC,,
I changed my code
if(i%j==0) sw=1;
to
if(i%j==0){sw=1; break;}
Thanks