C# Trial division - first n primes. Error in logic?

Question

In a course a problem was to list the first n primes. Apparently we should implement trial division while saving primes in an array to reduce the number of divisions required. Initially I misunderstood, but got a working if slower solution using a separate function to test for primality but I would like to implement it the way I should have done.

Below is my attempt, with irrelevant code removed, such as the input test.

using System;
namespace PrimeNumbers
{
    class MainClass
    {
        public static void Main (string[] args)
        {
            Console.Write("How many primes?\n");
            string s = Console.ReadLine();
            uint N;
            UInt32.TryParse(s, out N)
            uint[] PrimeTable = new uint[N];
            PrimeTable[0] = 2;
            for (uint i=1; i < N; i++)//loop n spaces in array, [0] set already so i starts from 1
            {
                uint j = PrimeTable[i -1] + 1;//sets j bigger than biggest prime so far
                bool isPrime = false;// Just a condition to allow the loop to break???(Is that right?)
                while (!isPrime)//so loop continues until a break is hit
                {
                    isPrime = true;//to ensure that the loop executes
                    for(uint k=0; k < i; k++)//want to divide by first i primes
                    {
                        if (PrimeTable[k] == 0) break;//try to avoid divide by zero - unnecessary
                        if (j % PrimeTable[k] == 0)//zero remainder means not prime so break and increment j
                        {
                            isPrime = false;
                            break;
                        }
                    } 
                    j++;//j increment mentioned above
                }
                PrimeTable[i] = j; //not different if this is enclosed in brace above
            }
            for (uint i = 0; i < N; i++)
                Console.Write(PrimeTable[i] + " ");
            Console.ReadLine();
        }
    }
}

My comments are my attempt to describe what I think the code is doing, I have tried very many small changes, often they would lead to divide by zero errors when running so I added in a test, but I don't think it should be necessary. (I also got several out of range errors when trying to change the loop conditions.)

I have looked at several questions on stack exchange, in particular: Program to find prime numbers The first answer uses a different method, the second is close to what I want, but the exact thing is in this comment from Nick Larsson:

You could make this faster by keeping track of the primes and only trying to divide by those.

C# is not shown on here: http://rosettacode.org/wiki/Sequence_of_primes_by_Trial_Division#Python

I have seen plenty of other methods and algorithms, such as Eratosthenes sieve and GNF, but really only want to implement it this way, as I think my problem is with the program logic and I don't understand why it doesn't work. Thanks

You might also want to look at Eratosthenes Sieve as an approach for tackling the smaller primes: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes — Lazarus, Nov 15 '15 at 11:59

score 2 · Accepted Answer · answered Nov 15 '15 at 12:25

The following should solve your problem:

    for (uint i = 1; i < numberOfPrimes; i++)//loop n spaces in array, [0] set already so i starts from 1
    {
        uint j = PrimeTable[i - 1] + 1;//sets j bigger than biggest prime so far

        bool isPrime = false;// Just a condition to allow the loop to break???(Is that right?)
        while (!isPrime)//so loop continues until a break is hit
        {
            isPrime = true;//to ensure that the loop executes
            for (uint k = 0; k < i; k++)//want to divide by first i primes
            {
                if (PrimeTable[k] == 0) break;//try to avoid divide by zero - unnecessary
                if (j % PrimeTable[k] == 0)//zero remainder means not prime so break and increment j
                {
                    isPrime = false;
                    j++; 

                    break; 
                }
            }

        }
        PrimeTable[i] = j; 
    }

The major change that I did was move the incrementation of the variable j to inside the conditional prime check. This is because, the current value is not prime, so we want to check the next prime number and must move to the next candidate before breaking in the loop.

Your code was incrementing after the check was made. Which means that when you found a prime candidate, you would increment to the next candidate and assign that as your prime. For example, when j = 3, it would pass the condition, isPrime would still = true, but then j++ would increment it to 4 and that would add it to the PrimeTable.

Make sense?

Enigmativity · Answer 2 · 2015-11-15T20:51:48.437

1

This might not be a very good answer to your question, but you might want to look at this implementation and see if you can spot where yours differs.

int primesCount = 10;
List<uint> primes = new List<uint>() { 2u };
for (uint n = 3u;; n += 2u)
{
    if (primes.TakeWhile(u => u * u <= n).All(u => n % u != 0))
    {
        primes.Add(n);
    }
    if (primes.Count() >= primesCount)
    {
        break;
    }
}

This correctly and efficiently computes the first primesCount primes.

edited Nov 15 '15 at 20:51

answered Nov 15 '15 at 11:47

Enigmativity

113,464
11
89
172

1

This returns 7703 as the 1000th prime, the 1000th prime is supposed to be 7919. I might have missed something in your algorithm though. – Thomas Lindvall Nov 15 '15 at 12:05
@ThomasLindvall Well spotted - it seems by inspection to include squares of odd primes as primes. – Luskentyrian Nov 15 '15 at 12:29
1

The error was the `<` rather than `<=` when checking the squares. – Enigmativity Nov 15 '15 at 20:52
private static bool isPrime(int i) { var root = Math.Sqrt(i); for (int n = 2; n <= root; n++) { if (i % n == 0) { return false; } } return true; } I use this, the fastest way I've managed to solve it, but your more functional approach is really cool. – Thomas Lindvall Nov 16 '15 at 08:48
@ThomasLindvall - computing `Math.Sqrt(i)` is very slow. You're far better off comparing `n * n <= i`. – Enigmativity Nov 16 '15 at 10:52

C# Trial division - first n primes. Error in logic?

2 Answers2