# Generating prime numbers using segmented Sieve

22 Jul 2016

Segmented Sieve allows you to extend the Sieve algorithm to list all prime numbers between two large integer numbers.

Following code sample shows solution written during my college days, for problem posted on SPOJ [Prime Generator]

``````using System;
using System.IO;
class Program
{
static int Idx, Size, BytesRead, OutPutBuffSize, WritePointer;
static byte[] Buffer, OutBuff;
public static void Initialze()
{
WriteStream = Console.OpenStandardOutput();
Idx = BytesRead = WritePointer = 0;
Size = 1 << 12; OutPutBuffSize = 1 << 12;
Buffer = new byte[Size]; OutBuff = new byte[OutPutBuffSize];
}

{
bool neg = false;
{
}
int m = _ReadByte - '0', r;
while ((r = ReadByte() - '0') >= 0) m = m * 10 + r;
return neg ? -m : m;
}
{
Idx = 0;
if (BytesRead < 1) Buffer[0] = 32;
}
{
return Buffer[Idx++];
}
public static void Dispose()
{
WriteStream.Write(OutBuff, 0, WritePointer);
WriteStream.Flush();
WriteStream.Close();
}
private static void WriteLineToBuffer(string s)
{
for (int i = 0; i < s.Length; i++)
{
if (WritePointer == OutPutBuffSize)
{
WriteStream.Write(OutBuff, 0, OutPutBuffSize);
WriteStream.Flush();
WritePointer = 0;
}
OutBuff[WritePointer++] = (byte)s[i];
}
if (WritePointer == OutPutBuffSize)
{
WriteStream.Write(OutBuff, 0, OutPutBuffSize);
WriteStream.Flush(); WritePointer = 0;
}
OutBuff[WritePointer++] = 10;
}
static void Main(string[] args)
{
Initialze();
int n, m, Max, j, N = 0, k; N = ReadInt();
bool[] prime = new bool[31624];
int limit = 178;
for (int i = 3; i < limit; i += 2)
if (!prime[i]) for (k = i * i; k < 31624; k += i)
prime[k] = true;
while (N-- > 0)
{
Max = (int)Math.Sqrt(m); p = new bool[m - n + 2]; if (n <= 1)
{
p[0] = true; if (n == 0) p[1] = true;
}
int div; //Do seperately for single even prime number
j = 2;
div = (n / j);
k = div * j;
if (k < n) k = (div + 1) * j;

for (; k <= m; k += j)
{
if (k == j) continue;
p[k - n] = true;
}
for (j = 3; j <= Max; j += 2)
if (!prime[j])
{
div = (n / j);
k = div * j;
if (k < n) k = (div + 1) * j;

for (; k <= m; k += j)
{
if (k == j) continue;
p[k - n] = true;
}
}
Max = m - n;
if (n < 3) WriteLineToBuffer("2");
j = (n % 2 == 0) ? 1 : 0;
for (; j <= Max; j += 2)
if (!p[j]) WriteLineToBuffer((n + j) + "");
}
Dispose();
}
}``````

Sample execution :

``C:/PROGRAM.EXE in.txt``

Sample input(in.txt):

``````2
2 10
11 15
``````

Sample output :

``````2
3
5
7
11
13``````

Share your ideas on further optimization if any ?