The 2000 first primes

ddanbe 0 94 Views

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!

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;
                }
            }           
        }
    }
}
Member Avatar for subtercosm
subtercosm 0 Light Poster

I love it!

Member Avatar for ddanbe
ddanbe 2,724 Professional Procrastinator

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.

Edit Preview