Introduction

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:

  1. 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.
  2. 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

using System;
using System.Collections.Generic;
using System.Linq;

public class Test
{
	private const int Max = 100000;
        public static void Main(string[] args)
        {
            if (args == null) throw new ArgumentNullException(nameof(args));
            var primeSet = PrimeSieve();

            var t = int.Parse(Console.ReadLine() ?? "0");
            while (t-- > 0)
            {
                var range = PopulateRange();
                PrintPrimes(range[0], range[1], primeSet);
            }
        }

        private static List<int> PrimeSieve()
        {
            // initialise a boolean array to true
            var isPrime = new bool[Max];
            for (var i = 0; i < Max; i++)
            {
                isPrime[i] = true;
            }

            for (var i = 2; i * i < Max; i++)
            {
                // if prime is not changed, then it's a prime
                if (!isPrime[i])
                {
                    continue;
                }
                // less than square are already marked
                for (var j = i * i; j < Max; j += i)
                {
                    isPrime[j] = false;
                }
            }

            var set = new List<int>();
            // return all the prime numbers
            for (var i = 2; i < Max; i++)
            {
                if (isPrime[i])
                {
                    set.Add(i);
                }
            }
            return set;
        }
        private static void PrintPrimes(long l, long r, List<int> primeSet)
        {
            // initialise the boolean range
            var range = r - l + 1;

            var isPrime = new bool[range];
            // 0 denotes the l and range denotes r
            // 1 should not be shown as prime number
            // if l = 1, then isPrime[0] should be false
            // for l == 1, we skip the 0 index and uses 1
            for (var i = l == 1 ? 1 : 0; i < range; i++)
            {
                isPrime[i] = true;
            }
            foreach (var prime in primeSet)
            {
                if (prime > r)
                {
                    break;
                }

                var closestL = prime * (l / prime);

                // range 24 to 50
                // prime is 5
                // 24 / 5 * 5 => 20
                // base < l then, 20 + 5 = 25
                if (closestL < l)
                {
                    closestL += prime;
                }

                if (closestL > r)
                {
                    continue;
                }

                // range 1 to 5
                // prime is 2
                // 1 / 2 * 2 => 0
                // base < l then, 0 + 2 = 2
                // base == l then add again because 2 is a prime number
                for (var j = closestL == prime ? closestL + prime : closestL; j <= r; j += prime)
                {
                    isPrime[j - l] = false;
                }
            }

            for (var i = 0; i < range; i++)
            {
                if (isPrime[i])
                {
                    Console.WriteLine(i + l);
                }
            }
        }
        private static long[] PopulateRange()
        {
            var range = new long[2];

            var i = 0;
            var line = Console.ReadLine();
            if (line == null)
            {
                return range;
            }
            foreach (var input in line.Split(' ').Select(long.Parse))
            {
                range[i++] = input;
            }

            return range;
        }
}
C# Program