Calculate prime numbers

Question

This is a program to calculate the largest prime number. Are there any possible improvements in style/speed/accuracy?

public static int? LargestPrime(int max)
{
    if (max < 0)
        return null;
    int largestPrime = 0;
    for (int i = 0; i <= max; i++)
    {              
        bool? isPrime = IsPrime(i);
        if ((bool)isPrime)
            largestPrime = i;
        if (i % 100000 == 0)
            Console.WriteLine(largestPrime.ToString("N0"));
    }
    return largestPrime;
}
private static List<int> listPrimes = new List<int>() { 2, 3 };
private static int listPrimeMax;
private static int listPrimesCount = 100000;
private static bool firstA = true;
private static bool firstB = true;
public static bool? IsPrime(int n)
{    
    if (listPrimes.Count < listPrimesCount)
    {
        // from wiki
        // function is_prime(n : integer)
        // if n ≤ 1
        //     return false
        // else if n ≤ 3
        //     return true
        // else if n mod 2 = 0 or n mod 3 = 0
        //     return false
        // let i ← 5
        // while i×i ≤ n
        //     if n mod i = 0 or n mod(i + 2) = 0
        //         return false
        //     i ← i + 6
        //return true
        if (n < 0)
            return null;
        if (n <= 1)
            return false;
        if (n <= 3)
            return true;
        if (n % 2 == 0 || n % 3 == 0)
            return false;
        for (int i = 5; i*i <= n; i += 6)
        {
            if (n % i == 0 || n % (i + 2) == 0)
                return false;
        }
        if (listPrimes.Count < listPrimesCount)
        {
            listPrimes.Add(n);
            listPrimeMax = n;
        }
        return true;
    }
    else
    {
        if(firstA)
        {
            Console.WriteLine("in listPrimes");
            firstA = false;
        }
        foreach (int i in listPrimes)
        {
            if (n % i == 0)
                return false;
            if (i * i > n)
                break;
        }
        for (int i = listPrimeMax + 2; i*i <= n; i += 2)
        {
            if (n % i == 0)
                return false;
        }
        if (listPrimes.Count < 100 * listPrimesCount)
        {
            listPrimes.Add(n);
            listPrimeMax = n;
        }
        else if(firstB)
        {
            Console.WriteLine("in 100*listPrimes");
            firstB = false;
        }
        return true;
    }           
}

Answer 1

public static int? LargestPrime(int max)
{
    if (max < 0)
        return null;
    int largestPrime = 0;
    for (int i = 0; i <= max; i++)
    {              
        bool? isPrime = IsPrime(i);
        if ((bool)isPrime)
            largestPrime = i;
        if (i % 100000 == 0)
            Console.WriteLine(largestPrime.ToString("N0"));
    }
    return largestPrime;
}  

• Omitting braces {}, although they might be optional, won't do you good in the long run because it makes your code error-prone.

• If an argument of a method isn't correct like max < 0 you should throw either an ArgumentException or better an ArgumentOutOfRangeException.

• You are iterating from 0 to max to check if the value is a prime, but I wonder what else could the number be? Either it is a prime or it isn't a prime, there is no third way so it doesn't make sense that IsPrime() returns a nullable bool.

---

bool? IsPrime(int n)

Here you are iterating from 5 to i*i<n for each number which is passed to the method.

So let us assume that we pass max = 10.000.000 (the dots are there for clearity) this

    if (n % i == 0 || n % (i + 2) == 0)
        return false;

in the for loop in the IsPrime() method is executed 16.194.513 times.

By using a sieve you could pretty much speed this thing up like so

static int CalculateLargestPrime(int maxPrime)
{
    bool[] isComposite = new bool[maxPrime + 1];
    for (int x = 2; x * x <= maxPrime; x++)
    {
        if (!isComposite[x])
        {
            for (int y = x * x; y <= maxPrime; y = y + x)
            {
                isComposite[y] = true;
            }
        }
    }
    for (int i = maxPrime; i >= 0; i--)
    {
        if (!isComposite[i])
        {
            return i;
        }
    }

    return -1;
}  

taken and adjusted from https://codereview.stackexchange.com/a/62158/29371

Answer 2

IsPrime

This method should throw an exception if the number is less then 0. Consequently you would the be able to return a clean boolean value. What does the null mean anyway - maybe?

A number can be either a prime or not or there is an error. This would make other parts of the code much easier because you wouldn't have to cast it.

Why do you need the listPrimes there? This is a very strange design. You add values to it but you never use it, only the Count property. For this a simple counter would be more adequate. I don't understand why you need it.

On the other side it should be just primes. We don't use type prefixes in C#. Among other variables the listPrimeMax is super confusing and misleading. It suggests it's a list but instead it's an int.

firstA firstB

They don't make any sense and their names don't help to understand their purpose either.

Answer 3

Any improvements in style / speed / accuracy / ..?

public static int? LargestPrime(int max)
{
    if (max < 0)
        return null;
    int largestPrime = 0;
    for (int i = 0; i <= max; i++)
    {              
        bool? isPrime = IsPrime(i);

There's a massive improvement in speed right there. If we end up returning max - 3 then why do we care whether max - 2000000 is prime or not? So

 public static int? LargestPrime(int max)
 {
     if (max < 2) return null;
     for (int i = max; true; i--)
     {
         if (IsPrime(i)) return i;
     }
 }

As to faster ways of testing primality, there must be hundreds of answers covering the topic already. I suggest reading top-voted answers in the primes tag.

Answer 4

Based on the accepted answer ended up with this
With BitArray limited to Int32.Max
But it does up to Int32.Max in 4 minutes

class Program
{
    static void Main(string[] args)
    {
        Int32 maxPrime;
        if (args.Count() == 0)
            maxPrime = Int32.MaxValue-1;
        else
            maxPrime = Int32.Parse(args[0]);
        try
        {
            int lastPrime = GetAllPrimesLessThan(maxPrime);
            Console.WriteLine("Max prime = " + lastPrime.ToString("N0"));
            Console.ReadLine();
        }
        catch (Exception ex)
        { Console.WriteLine(ex.ToString()); }
    }
    private static int GetAllPrimesLessThan(Int32 maxPrime)
    {           
        if (maxPrime > Int32.MaxValue - 1 || maxPrime < 0)
            throw new IndexOutOfRangeException();
        int lastPrime = 0;
        System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
        sw.Start();
        var maxSquareRoot = (int)Math.Sqrt(maxPrime);
        var eliminated = new BitArray(maxPrime + 1);
        int count = 0;
        Console.WriteLine("GetAllPrimesLessThan starting loop sw " + sw.ElapsedMilliseconds.ToString("N0"));
        for (int i = 2; i <= maxPrime; ++i)
        {
            if (!eliminated[i])
            {
                count++;
                lastPrime = i;
                if(count % 1000000 == 0 || count <= 1000)
                    Console.WriteLine("Current % 1,000,000 || <= 1000 = " + i.ToString("N0"));
                if (i <= maxSquareRoot)
                    for (int j = i * i; j <= maxPrime && j > 0; j += i)
                        eliminated[j] = true;
            }
        }
        Console.WriteLine("GetAllPrimesLessThan end sw " + sw.ElapsedMilliseconds.ToString("N0"));
        return lastPrime;
    }
}