OJ Board

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

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

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.

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

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

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

see you!!!
y salusos desde Margarita !!

deleted

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.

Thank you.
It is now accepted.

I have the same problem!?! Can someone help me??? Please!!

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]

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.

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.

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