Peter wants to generate some prime numbers for his cryptosystem. Help him! Your task is to generate all prime numbers between two given numbers!

Constraints

The input begins with the number t of test cases in a single line (t<=10). In each of the next t lines there are two numbers m and n (1 <= m <= n <= 1000000000, n-m<=100000) separated by a space.

Input:
2
1 10
3 5
Output:
2
3
5
7
3
5

Approach

We generate prime numbers from 2 to the rightmost possible, but in this case the rightmost entry is huge. We see that the range of numbers denoted by n - m can be Max (100000).

Why Square Root or i*i < Max?

Square root of 100 is 10. Let's say a x b = 100, if one number increases the other number decreases.

i.e. 20 x 5 = 100,

We cover this case for 5 that is the numbers less than 10 while finding multiples of 5.

Steps

We will use this information, and follow the below steps:

We can generate the prime numbers from 0 to Max. a. Initialise a boolean array IsPrime of size Max and set to true b. We loop from i till i * i is less than Max c. Start an inner loop if IsPrime is true, from j = i*i to Max and increment in i steps, continue setting to false because it's a multiple. d. Use the IsPrime to generate and return the PrimeSet upto Max.

We generate from Left to Right by using the multiples in the PrimeSet obtained in the Step #1 a. Initialise IsPrime boolean array for the range and set to true except for left set to 1. b. find the closest point in the left (first multiple lies in the range) and update the isPrime for the subsequent multiples in the range. c. Print the range by keeping the left as offset.

Code

You've successfully subscribed to Coding Today

Great! Next, complete checkout for full access to Coding Today

Welcome back! You've successfully signed in.

Unable to sign you in. Please try again.

Success! Your account is fully activated, you now have access to all content.