program that checks if any even number greater than 4 is a sum of two prime numbers

Question

I have the following problem:
Given that the even numbers greater than 4 can be obtained by addition of 2 prime numbers, I have to write an algorithm which check it. The algorithm should take less time that O(n^2).

For example there is a set of numbers from 6 to n. If we have the number 6 the answer is 6=3+3 and for 22=17+5 and so on.

My first idea:

S - set of n numbers
for i=1 to n {
  //removing odd numbers
   if (S[i]%2!=0)
      continue;

   result = false;
   for j=2 to S[i]-2{
       if (j.isPrime) // prime test can be done in O(log^2(n))
          if ((S[i]-j).isPrime)
               result = true;
               break;
          else
               continue;
   }

   if (result == false)
       break;
}

Since I use 2 for-loops, the total running time of this algorithm should be O(n*n)*O(log^2(n)) = O(n^2*log^2(n)) which is not less than O(n^2). Does anybody have an idea to reduce the running time to get the required time of less than O(n^2)?

Jarosław Gomułka · Answer 1 · 2012-04-01T15:22:15.873

2

If set contains big numbers I've got nothing.

If max(S) < n ^ 2 / log(n) than:

You should preprocess which numbers from interval [1, max(S)] are primes. For preprocessing you can use sieve of Eratosthenes

Then, you are able to check if number is a prime in O(1) and complexity of your solution becomes O(N^2).

edited Apr 01 '12 at 15:22

answered Apr 01 '12 at 15:12

Jarosław Gomułka

4,935
18
24

Your idea sounds good, but unfortunately I have to do it in LESS than O(n^2). – Viv Apr 01 '12 at 16:26
I just have idea. There are approx. n / lg (n) prime numbers that are <= n (http://en.wikipedia.org/wiki/Prime_number#Number_of_prime_numbers_below_a_given_number). If you select random 10 * lg(n) prime numbers, than there is good chance that you select prime number X, that N - X is also a prime. – Jarosław Gomułka Apr 01 '12 at 19:43

score 1 · Answer 2 · answered Apr 02 '12 at 12:13

This is Goldbach's conjecture. Primality testing is known to be in P (polynomial time), but the break-even is ridiculously high - in practice, you will not be able to do this in anywhere near O(n^2).

If we assume you only need to deal with relatively small numbers, and can precompute the primes up to a certain limit, you still need to find candidate pairs. The prime counting function gives approximately:
n / ln(n) primes, less than (n). Subtracting the candidate prime (p) from (n) gives an odd number (q). If you can look up the primality of (q) with a complexity of: n.ln(n), or better - i.e., an O(1) lookup table for all odd numbers less than the limit - you can achieve O(n^2) or better.

score 0 · Answer 3 · edited May 23 '17 at 11:56

0

You can run only until square root of N, this sufficient for determine if the number is prime or not.
this will reduce your running time.

also take a look at the following question - Program to find prime numbers

edited May 23 '17 at 11:56

Community

1
1

answered Apr 01 '12 at 15:16

Dor Cohen

16,769
23
93
161

program that checks if any even number greater than 4 is a sum of two prime numbers

3 Answers3