PRIME1 - Prime Generator

SPOJ : Question

Given a range [n , m], you have to print all the prime numbers between n and m both inclusively.

Hint 1 :

Sieve of Eratosthenes.

Hint 2 :

see the constraints 

range of m , n : ( 1 <= m <= n <= 1000000000 )

since the max range is 10^9 so we directly do not apply Sieve to find all the prime numbers between 1 and 10^9 because of lack of memory ( we have only at max 10^7 size of the array ).

So now what we have done? 😟

Let's check the constraints again.

The difference between n and m will not cross 10^5  ( n-m<=100000 )

Yahoo 😃 , So we can iterate over the given range.

What is the benefit of this ( iteration over given range ) 🤔 .

Hint 3:

By iterating over the range we can check for each number whether its a prime or not.

This takes O(n-m).

And for check number is prime or not, make a loop up to the square root of a number , if any number up to the sqrt of number divides the given number then it is not a prime, otherwise, it's a prime number and we print it.

But wait, think our task complete?

This take O( (n-m) * sqrt(num) )

The number is in between 1 and 10^9, so the worst sqrt(num) = sqrt(10^9) ≃ 10^4

So the complexity is O( 10^5 * 10^4 ) = O( 10^9 ).

By this complexity, it is impossible to solve this question in 6sec(given).

But if we already have all the prime numbers ≤ 10^5. Then we do not have to iterate from 2 to sqrt(num)  instead we go iterate over only the prime numbers from 2 to sqrt(num). This will reduce a large amount of time.

How we already have all the prime number ≤ 10^5? 🤔

Hint 4: Solution

#include<bits/stdc++.h>

using namespace std;

#define MAX 1000006

bool isprime[MAX];

vector<int> prime;

void sieve(){

    for( int i = 0; i < MAX; i++ ){

        isprime[i] = true;

    }

    isprime[1] = isprime[0] =  false;

    for( int i = 2; i * i < MAX; i++ ){ // make prime upto 1000006

        if( isprime[i] ){

            for( int j = i * 2; j < MAX; j += i ){

                if( j % i == 0 ){

                    isprime[j] = false;

                }

            }

        }

    }

}

void gen_prime(){

    for( int i = 0; i < MAX; i++ ){

        if( isprime[i] ){

            prime.push_back(i);  // store the prime numbers

        }

    }

}

int main()

{

    sieve(); // call sieve

    gen_prime(); // call for store the primes

    int t;

    cin >> t;

    while( t-- ){

        long int a , b;

        cin >> a >> b;

        for( long int i = a; i <= b; i++ ){

            bool flag = true;

            for( int j = 0; prime[j]*prime[j] <= i; j++ ){

                if( i % prime[j] == 0 ){

                    flag = false;

                    break;

                }

            }

            if( flag && i != 1 ){

                cout << i << endl;

            }

        }

    }

}