Blink and you will see them appear in a Console window.
This is a translation to C# of a Modula-2 implementation by N.Wirth, the inventor of Pascal. The tested integers are obtained by incrementing alternatively by 2 and 4, thereby avoiding multiples of 2 and 3 in the first place. This list starts with 5, assuming 2 and 3 are already known primes. Divisibility needs to be tested for prime divisors only, which are obtained by storing previously computed results. This algorithm is a little bit hazier then the traditional "sieve" algorithm. But it is fun to play computer yourself and figure out how it works!
The 2000 first primes
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;
}
}
}
}
}
subtercosm 0 Light Poster
I love it!
ddanbe 2,724 Professional Procrastinator Featured Poster
Just did a translation, which was not even hard to do.
To find out how it works was pure fun!
Be a part of the DaniWeb community
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.