543  Goldbach's Conjecture
Moderator: Board moderators
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
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
Re: right u r
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.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 .
Here's a sieve:
[c]
if (isprime[(i2)/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.
543, I don't understand the Sample Input
Why 8 = 3 + 5 if 8 = 1 + 7, where ba is maximized !!!
is this a error, or i'm wrong ????
is this a error, or i'm wrong ????
 Ghust_omega
 Experienced poster
 Posts: 115
 Joined: Tue Apr 06, 2004 7:04 pm
 Location: Venezuela
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 !!
see you!!!
y salusos desde Margarita !!
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:
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.
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=na;
if(primes[b]==1) {
printf("%ld=%ld+%ld\n",n,a,b);
flag=1;
break;
}
}
the if condition should be..
if( primes[a] == 1 && primes == 1 ) {
//
//
}
Hope it helps.
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(ni)) 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.

 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]
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]
Re: 543  Time Limit with C, compile Error with Java. GAAAA!
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 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; } } }

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