CODEWITHSUNDEEP
performanceprimes
Viv
Viv

Reputation: 21

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

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)?

Upvotes: 2

Views: 1629

Answers (3)

Brett Hale
Brett Hale

Reputation: 22328

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.

Upvotes: 1

Jarosław Gomułka
Jarosław Gomułka

Reputation: 4995

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).

Upvotes: 2

Dor Cohen
Dor Cohen

Reputation: 17090

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

Upvotes: 0

Related Questions