543 - Goldbach's Conjecture

All about problems in Volume 5. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

Post by kiha » Fri Mar 05, 2004 8:05 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

Post by sumankar » Mon Mar 08, 2004 9:07 am

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 :D

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam » Sat Mar 13, 2004 3:47 pm

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

Post by Minilek » Wed Aug 04, 2004 8:59 am

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. :D

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

543, I don't understand the Sample Input

Post by Boss » Sat Nov 27, 2004 8:26 pm

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

User avatar
Ghust_omega
Experienced poster
Posts: 115
Joined: Tue Apr 06, 2004 7:04 pm
Location: Venezuela

Post by Ghust_omega » Mon Nov 29, 2004 6:48 am

Hi!! Boss I see you are from Venezuela nice :wink: 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 !!

Post by Boss » Tue Nov 30, 2004 4:10 pm

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
Location: Bangladesh

543

Post by eshika » Mon Dec 27, 2004 12:00 pm

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

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

minor mistakes...

Post by sohel » Mon Dec 27, 2004 1:24 pm

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. :wink:

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

Post by eshika » Wed Dec 29, 2004 11:20 am

Thank you.
It is now accepted.

tudalex
New poster
Posts: 1
Joined: Sun Mar 20, 2005 10:29 pm

Post by tudalex » Sun Mar 20, 2005 10:33 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
     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
New poster
Posts: 2
Joined: Wed May 11, 2005 4:53 am

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

Post by feliperibeiro » Wed May 11, 2005 4:57 am

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]

User avatar
J&Jewel
New poster
Posts: 50
Joined: Thu Jul 31, 2003 10:43 am
Location: Daffodil University,Dhaka,Bangladesh
Contact:

Post by J&Jewel » Wed May 25, 2005 10:42 am

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.
I hate Wrong Answer!

User avatar
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!

Post by dumb dan » Wed May 25, 2005 1:00 pm

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

Post by feliperibeiro » Wed May 25, 2005 4:21 pm

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

Post Reply

Return to “Volume 5 (500-599)”