0

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;
                }
            }           
        }
    }
}
2
Contributors
2
Replies
4
Views
8 Years
Discussion Span
Last Post by ddanbe
0

Just did a translation, which was not even hard to do.
To find out how it works was pure fun!

Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.