## 543 - Goldbach's Conjecture

Moderator: Board moderators

kiha
New poster
Posts: 37
Joined: Sat Dec 20, 2003 10:59 pm
Yeeeeah, of course

Sorry for this, I was sent a private message telling that Sieve of Erastothenes if of course faster and I also asked my classmate who told me that c/c++ is faster than Pascal.
However, thanks

With regards
kiha

sumankar
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:

### Hi

before u go on to sieve (i.e if u aren't already into it)
here's a suggestion:

improve that very algorithm,
think of the situation when u need to divide
a number by any even number when testing for
primality.
There 's only 1 even prime number :that's 2,
and then you can speed up u'r twice by cutting doen on the
unnecessary checks.

The moral is:
even this algo works in most problems

regards
Suman

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:
i don't know whether pascal is slower than c or c++, but i know many topcoders using pascal .
--
Anupam
"Everything should be made simple, but not always simpler"

Minilek
Learning poster
Posts: 90
Joined: Tue Jul 27, 2004 9:34 am
Location: Cambridge, MA
Contact:

### Re: right u r

Riyad wrote: ++++ martin , as a matter of regret i heard about the algorithm sieve of Erasthostenes. but i dont feel tempted to write one my self .
Hm..I think writing a sieve is not as hard as you think it is. As a matter of fact, it's shorter than your isPrime() function.

Here's a sieve:

[c]
if (isprime[(i-2)/2]) {
primes[pind++] = i;
for (j=3;j*i<=999999;j+=2) isprime[(j*i - 2)/2] = 0;
}
[/c]

And the actual sieve part is only the line with the for loop. I tried 2 submissions: one by checking all odd divisors up to sqrt, and one with sieve. Sieve got me AC in .334 seconds and checking to sqrt was like 1.7+ seconds. So for less work you get better speed.

Boss
New poster
Posts: 5
Joined: Sat Nov 20, 2004 9:54 pm
Location: Venezuela
Contact:

### 543, I don't understand the Sample Input

Why 8 = 3 + 5 if 8 = 1 + 7, where b-a is maximized !!!
is this a error, or i'm wrong ????

Ghust_omega
Experienced poster
Posts: 115
Joined: Tue Apr 06, 2004 7:04 pm
Location: Venezuela
Hi!! Boss I see you are from Venezuela nice well 1 is not prime, the primes numbers definition says. Take that in count and the problem can be solved ...
Hope it Helps
Keep posting !!

Boss
New poster
Posts: 5
Joined: Sat Nov 20, 2004 9:54 pm
Location: Venezuela
Contact:

### ok !!

AH ok man, thanks.... the problem is Ready, now I will solve the conjecture part II... number 686

see you!!!
y salusos desde Margarita !!

eshika
New poster
Posts: 11
Joined: Sat Oct 02, 2004 12:02 pm

### 543

deleted
Last edited by eshika on Wed Dec 29, 2004 11:17 am, edited 1 time in total.

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

### minor mistakes...

Hi,

There are two small mistakes in your code..

1] You must print a space between every number and operators.
-> Correct output should be 8 = 3 + 5
and not 8=3+5

2] Consider this part of your code:

Code: Select all

``````while(scanf("%ld",&n)==1)
{
if (n==0) break;
for(a=3;a<MAX;a+=2)
{
b=n-a;
if(primes[b]==1) {
printf("%ld=%ld+%ld\n",n,a,b);
flag=1;
break;
}
}
``````
Remember, both the numbers must be prime and from what it looks, you are only checking for the second number.

the if condition should be..
if( primes[a] == 1 && primes == 1 ) {
//
//
}

Hope it helps.

eshika
New poster
Posts: 11
Joined: Sat Oct 02, 2004 12:02 pm
Thank you.
It is now accepted.

tudalex
New poster
Posts: 1
Joined: Sun Mar 20, 2005 10:29 pm
I have the same problem!?! Can someone help me??? Please!!

Code: Select all

``````var i,n,p:longint;
f:text;
a:array[1..2,1..1000] of longint;
function prim(x:longint):boolean;
var i:longint;
begin
prim:=true;
for i:=2 to trunc(sqrt(x)) do if x mod i=0 then begin prim:=false; break; end;
end;
begin
while n>0 do
begin
for i:=3 to n do if (prim(i)) and (prim(n-i)) then begin p:=p+1; a[1,p]:=n; a[2,p]:=i; break; end;
end;
for i:=1 to p do writeln(a[1,i],' = ',a[2,i],' + ',a[1,i]-a[2,i]);
end.``````

feliperibeiro
New poster
Posts: 2
Joined: Wed May 11, 2005 4:53 am

### 543 - Time Limit with C, compile Error with Java. GAAAA! :O

Hello folks,
take a look at this code, for question 543, what's causing Time Limit?

[code]
[c]
#define SIZE 1000000

char flags[SIZE+1];

void sieve(void){
long i, k;

for( i=0; i<=SIZE; i++ )
flags[i] = 1;

for( i=2; i<=SIZE; i++ ){
if( flags[i] )
for( k=i+i; k<=SIZE; k+=i )
flags[k] = 0;
}
flags[1]=0;
}

main() {
long numero;
sieve();
while(scanf("%ld",&numero)==1 && numero!=0) {
goldbach(numero);
}
return 0;
}

int goldbach(long numero) {
long i,j;
for(i = 1; i<numero; i+=2) {
for(j = i; j<numero; j+=2) {
if(isPrime(i) && isPrime(j) && i+j==numero) {

printf("%ld = %ld + %ld\n", numero,i,j);
return 0;
}

}

}
printf("Goldbach's conjecture is wrong.\n");
return 0;
}

int isPrime(long numero) {
return flags[numero];
}

[/code]

J&Jewel
New poster
Posts: 50
Joined: Thu Jul 31, 2003 10:43 am
Contact:
I saw ur program.....not fully....
but u print some where the goldback conjucture is not possible....but it is not possible to print it..

u can make a function that generate prime number index...
If need more help continue posting.

dumb dan
Learning poster
Posts: 67
Joined: Tue Aug 05, 2003 1:02 am

### Re: 543 - Time Limit with C, compile Error with Java. GAAAA!

feliperibeiro wrote:

Code: Select all

``````    for(i = 1; i<numero; i+=2) {
for(j = i; j<numero; j+=2) {
if(isPrime(i) && isPrime(j) && i+j==numero) {
printf("%ld = %ld + %ld\n", numero,i,j);
return 0;
}
}
}``````
This part of your program has complexity O(numero^2) where numero can be as big as 1000000. If you think about what you are doing a little more you'll soon see you can do this in O(numero) time.

feliperibeiro
New poster
Posts: 2
Joined: Wed May 11, 2005 4:53 am
Oh, i've already solved, this O(n