Wednesday, January 7, 2009

Calculates first 20000 prime numbers in C#

using System;
namespace Primes
{
class Program
{
static void Main(string[] args)
{
ListPrimes();
Console.ReadKey();
}
//Translation from Modula-2 to C#
//See N.Wirth "Programming in Modula-2, second ed."
public static void ListPrimes()
{
const uint N = 2000;
const uint M = 45; //+- sqrt(N)
const uint LL = 10; //no. of primes placed on a line
uint i, k, x = 1, inc = 4, lim = 1, square = 9, L = 0;
bool prime;
uint[] V = new uint[M];
uint[] P = new uint[M];
for (i = 3; i <= N; i++)
{
do //find next prime number p[i]
{
x = x + inc;
inc = 6 - inc;
if (square <= x)
{
lim++;
V[lim] = square;
square = P[lim + 1] * P[lim + 1];
}
k = 2; prime = true;
while (prime && (k < lim))
{
k++;
if (V[k] < x) V[k] = V[k] + 2 * P[k];
prime = x != V[k];
}
}

while (!prime);
if (i < M) P[i] = x;
Console.Write("{0,7}",x);
L++;
if (L == LL)
{
Console.WriteLine(); L = 0;
}
}
}
}
}

0 comments: