sum of two primes

[kimkim0513]

the program should check if all even integers from low to high can be written as the sum of two prime numbers

the lower limit low will be greater than 2
the upper limit high will not exceed 10000

assume both inputs for low and high are even

if all even integers in the interval can be expressed as the sum of two primes, print "Verified". Otherwise, print "Failed".

I have written some functions which may be useful...

bool is_prime(int n){
     for(int i = 2; i <= (n / 2); i++)
     {if(n % i == 0) return false;}
     return true;
     }

int nxt_prime(int n){
    if(is_prime(n)) return n;
    return nxt_prime(++n);
    }

I want to tackle the problem in:
take a test value (will loop it; low <= test <= high, each time increase test by 2)
break it down as n and test-n
first take n =2,

(**)
test if both n and test-n are prime
if not, take n to be the next prime

do (**)

could anyone help me in this?
i just spent tons of time on it
still can't the correct code....

[sfuo]

bool is_prime(int n)
{
     for(int i = 2; i <= sqrt(n); i++) <---- use sqrt(n)
     {if(n % i == 0) return false;}
     return true;
}

The algorithm is from 2 to sqrt(n) not n/2.

[kimkim0513]

oh thanks.. my function does unnecessary work :D

[ddanbe]

It still does!
Put sqrt(n) in a variable and test the variable in the for loop.
That way you avoid the overhead of calling the sqrt function too much.

[TrustyTony]

My algorithm would be something like this:

1) generate primes until 100 (100 * 100 = 10000), remove 2 (odd sum with other primes)
2) do double loop marking sums of two integers not marked before until 5000 marked (or just mark all sums
3) check that there was 5000 marks if brute force loop without counting marking unmarked.

[mrnutty]

>>the program should check if all even integers from low to high can be written as the sum of two prime numbers

So if one test fails in that range then the whole test fails? I'm sure I can prove that given a range of x to y
that there has to be at least one number that doesn't sum from 2 prime

[TrustyTony]

2 is not, but the condition stated lower bound more than 2 ie. 4 or bigger even number, so not all even. Also the two numbers must be allowed to be the same number, like 6=3+3