Finding primes in a range of numbers

The fastest way(yet easy to understand and implement) to test a prime number is Rabin-Miller Prime Test. However, it suffers from two issues:

• It is suitable for a single number
• It may give false positives

When it comes to finding primes from 1 to say 10^6. This method is not suitable. Since this method doesn't use any previously generated information. So the program will end up testing each number.

Sieve Algorithm on the other hand, uses previously generated results and works faster when determining the primes in a range.

Here is a code snippet for the same

Snippet

bool isprime[1000005];
memset(isprime,true,sizeof(isprime));
for(long long int i=2;i*i<1000005;i++){
  if(!isprime[i]) continue;
  for(long long int j=i*i;j<1000005;j=j+i){
   isprime[j]=false;
  }

Time Complexity

The outer loop run for O(n^1/2). While the inner runs for far less than n. Thus the total time complexity will be far lesser than O(N^1.5).

As per wikipedia, the complexity for this algorithm is O(n log log n).