1
\$\begingroup\$

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;
    }           
}
\$\endgroup\$
3
  • 1
    \$\begingroup\$ If you want the largest prime in LargestPrime, why don't you start the iteration from max down to zero? \$\endgroup\$
    – user73941
    Oct 10 '16 at 14:41
  • 1
    \$\begingroup\$ @HenrikHansen I really meant primes but that is how the question was written \$\endgroup\$
    – paparazzo
    Oct 10 '16 at 15:24
  • 1
    \$\begingroup\$ As negative values have no meaning in the context of primes, you could consider to use uint or maybe ulong instead of int. \$\endgroup\$
    – user73941
    Oct 10 '16 at 15:47
5
\$\begingroup\$
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

\$\endgroup\$
2
  • \$\begingroup\$ I don't follow. Will try and test it out. \$\endgroup\$
    – paparazzo
    Oct 10 '16 at 11:28
  • \$\begingroup\$ @Paparazzi Prime sieve works basically by taking advantage of the fact that when counting sequentially, If you mark off All the multiples of each number you count to (excluding 1 of course), You will be left with only the Primes without marks on them. (you mark the multiples starting with 2x, 3x, 4x, etc, DON'T mark X itself or it won't work) If a number already has a mark, it is definitely not prime, but you still have to mark ITS multiples starting at 2x. Example Below, Parenthesis show Each time a number has been marked 2 3 (4) 5 ((6)) 7 ((8)) (9) ((10)) 11 ((((12)))) 13 ((14)) \$\endgroup\$
    – DJHenjin
    Oct 10 '16 at 13:18
3
\$\begingroup\$

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.

\$\endgroup\$
9
  • \$\begingroup\$ Really don't use listPrimes? \$\endgroup\$
    – paparazzo
    Oct 10 '16 at 10:14
  • \$\begingroup\$ Small note - casting would be unnecessary if IsPrime would throw exception and in current form this casting is not working at all \$\endgroup\$ Oct 10 '16 at 10:18
  • \$\begingroup\$ @Paparazzi - you could try to explain that you are using the list when you've filled it with 100000 prime numbers but not before then. I'd be interested to hear your rationale for that anyway. \$\endgroup\$
    – RobH
    Oct 10 '16 at 10:20
  • 2
    \$\begingroup\$ Thx for the DV @Paparazzi but your code is still a mess and you know I'm right. If you cannot accept critique about your code then why do you ask for a review in the first place? \$\endgroup\$
    – t3chb0t
    Oct 10 '16 at 10:22
  • 1
    \$\begingroup\$ @Paparazzi do you ever explain yourself or do you think your code is so well written that the answer is obvious? I assure you it's not. \$\endgroup\$
    – RobH
    Oct 10 '16 at 10:28
3
\$\begingroup\$

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 tag.

\$\endgroup\$
1
  • \$\begingroup\$ I really meant all primes but that is the wording of the question. \$\endgroup\$
    – paparazzo
    Oct 10 '16 at 15:27
0
\$\begingroup\$

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;
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.