rafael859's blog

I came up with a nice little problem on computational complexity
By rafael859, 10 years ago, In English

A well-known problem is, given a prime number P, find the next smallest prime number. An algorithm to solve this is to go to P+1, check if it's prime by checking the divisibility of all numbers from 2 up to floor(sqrt(P+1)) (Because all prime divisors of a number will be smaller or equal to it's square root), then check the same for P+2, P+3 and so on, until a prime number is found. Prove that the complexity of this algorithm is O(P).

Solution:

According to Andrica's conjecture , for two prime numbers p and q with p < q and no other prime between them (q is the next smallest prime after p), sqrt(q) — sqrt(p) < 1 which becomes q < p + 2\sqrt(p) + 1 and since they are natural numbers, q <= p + 2*sqrt(p). Therefore, the gap between p and q is at most 2*sqrt(p).

This means that our algorithm will check at most 2*sqrt(p) numbers (or to be more precise, floor(2*sqrt(p)) ). For each number we will check up to its square root, therefore we will do floor(sqrt(p+1)) + floor(sqrt(p+2)) + floor(sqrt(p+3)) + ... + floor(sqrt(p + 2*floor(sqrt(p)))) operations in total. But all the elements are < floor(sqrt(p + p)) = floor(sqrt(2*p)). There are floor(sqrt(2*p)) elements, so the total number of operations is less than floor(sqrt(2*p))*floor(sqrt(2\p)) <= 2*p. Thus this algorithm will do up to 2*P operations and the complexity will be O(P).

  • Vote: I like it
  • +33
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You can use faster than O(sqrt(p)) primality tests.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Indeed but the whole point was to prove that this algorithm is faster than you'd expect it to be and the complexity is very pretty.

    → Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    Even if check is done in O(sqrt(p)) for each number it's still much faster then sqrt(p) * range especially if we know that there is no other primes.

    Each 2nd check is done in 1 operation (divisibility by two), echo 3rd of others in 2 operation, etc

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      That's a cool observation. Ignoring the fact that the prime-gap is relatively small for small numbers, can we get some better complexity for this algorithm using your observation?

      I tried to get prove a better one but with no success. I think it's obvious that O(P) is too much :P

      → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

A long time ago I set a problem about it. I couldn't find two consecutive prime numbers with at least 100 units gap. I bounded this value as ln(P) because I considered prime numbers to distribute in pretty uniform way. Are there any proofs or counter-examples for my assumptions?

→ Reply