CODEWITHSUNDEEP
javamathtime-complexityprimesasymptotic-complexity
giò
giò

Reputation: 3580

Complexity of print first n prime number

In an interview I was given this questions:

Write a function to print first n prime numbers

The function looks like this:

Live on ideone

while (true) {
  boolean isPrime = true; 
  for (int divisor = 2; divisor <= (int)(Math.sqrt(number)); divisor++) {
    if (number % divisor == 0) {
      isPrime = false;      
      break;
    }
  }
  number++;
  if(isPrime) {
    System.out.print(number + " ");
    primes++;
  }

  if (primes == n)
      break;
}

A simple complexity analysis could led to O(n√n)
But the interviewer said that the outerloop doesn't go to simply n because for example to find the first 100 prime numbers we need to loop to 541 (that is the 100th prime numbers)

So how do we express the time complexity given this?

Upvotes: 1

Views: 1736

Answers (1)

user1196549
user1196549

Reputation:

Answering this takes high math, namely the distribution law of the prime numbers. It tells you (https://en.wikipedia.org/wiki/Prime_number_theorem) that the value of the n-th prime number is about n.log(n).

Then your complexity is O(n√n.log(n)√log(n)).

I may turn out that this bound is pessimistic, because not all iterations run until √n. For instance, even numbers are detected immediately. For a tighter bound, you would need the distribution law of the smallest factor of the integers.

Upvotes: 5

Related Questions