543 - Goldbach's Conjecture

[kiha]

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

[sumankar]

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]

i don't know whether pascal is slower than c or c++, but i know many topcoders using pascal .
--
Anupam

[Minilek]

++++ 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]

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

[Ghust_omega]

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]

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]

deleted

[sohel]

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]

Thank you.
It is now accepted.

[tudalex]

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
     readln(n);
     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;
           readln(n);
     end;
     for i:=1 to p do writeln(a[1,i],' = ',a[2,i],' + ',a[1,i]-a[2,i]);
end.

[feliperibeiro]

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]

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]

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]

Oh, i've already solved, this O(n