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:
- We can generate the prime numbers from 0 to
Max
.
a. Initialise a boolean arrayIsPrime
of sizeMax
and set to true
b. We loop from i tilli * i
is less thanMax
c. Start an inner loop ifIsPrime
is true, from j =i*i
toMax
and increment ini
steps, continue setting to false because it's a multiple.
d. Use theIsPrime
to generate and return thePrimeSet
uptoMax
. - We generate from Left to Right by using the multiples in the
PrimeSet
obtained in the Step #1
a. InitialiseIsPrime
boolean array for the range and set to true except forleft
set to1
.
b. find the closest point in the left (first multiple lies in the range) and update theisPrime
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;
}
}