Calculating time complexity for finding first 'n' prime numbers

Question

The algorithm for finding first 'n' prime numbers is:

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

The book, "Introduction to java programming", calculates big-O for this algorithm as:

Since it takes √i steps in the for loop to check whether number i is prime, the algorithm takes √2 + √3 + √4 + ... + √n steps to find all the prime numbers less than or equal to n.

Observe that,

√2 + √3 + √4 + ... + √n <= n√n

Therefore, the time complexity for this algorithm is O(n√n).

Que:

1. He says, "it takes √i steps in the for loop to check whether number i is prime".

Don't you think it should be (√i-1) steps.

2. Please explain how

√2 + √3 + √4 + ... + √n <= n√n

(I know the relationship holds if you just replace 'n' with a random number. I need explanation)

Answer 1

1. Complexity-wise, subtracting 1 has no effect (and this is an informal introduction).
   (It's actually floor(√n) - 1.)

2. You have n - 1 terms. Adding √n n - 1 times:

   √n + √n + √n + ... + √n = (n-1)√n <= n√n

and since √2, √3, √4, ... are all less than √n, it follows that

√2 + √3 + √4 + ... + √n <= √n + √n + √n + ... + √n <= n√n

Answer 2

answer 2 :

for 0 < i <= n we have i <= n, therefore √i <= √n, so the sum of √i for i between 1 and n <= the sum of √n between 1 and n which √n + √n ... + √n, n times