How to find a number as a sum of prime numbers?

Question

Lets see we want to find all numbers between 1 to 1000 which are represented as a sum of two prime numbers. e.g 8 = 3+5, 24 = 13+11

Now this can be done in O(n^2) by iterating through the list of prime numbers between 1 to 1000.

Is there anyway of doing the same thing in less than O(n^2).Is there a method for doing this in linear time ?

Answer 1

For all the even numbers we know now, they can be represented as the sum of 2 prime numbers(see Goldbach's conjecture)

For all the odd numbers, if it can be represented as the sum of 2 prime numbers, one of the them must be 2, and the other should be an odd prime.

So the total number should be (1000/2 - 1) + (prime number count from 3 to 997),

in which,

(1000/2 - 1) is the total number of series 4, 6, 8, 10...

(prime number count from 3 to 997) is the total number of series 5(2+3), 7(2+5), 9(2+7), 13(2+11) ...

Answer 2

Make an array p of 1000 booleans. Set p[i] to true if i is prime, and false otherwise.

Then the O(N^2) algorithm becomes easy: go through numbers k 1 through 1000 in the outer loop, then go through all primes x greater than k in an inner loop, and check if there exists a prime such that p[k-x] is true:

for k in 1..1000
    for x in primes greater than k
        if (p[x-k])
            print k can be represented as x plus (x-k)
            break

I doubt that the check could be performed in constant time for a total running time of O(N) for the 1000 numbers, because computer-aided verification currently proceeds at a rather slow speeds.