I am new to C# programming. I wrote a little program in C# to calculate all primes until a user-given value. Ignoring the lack of computing power I wrote this program to handle theoretically very huge numbers.

The code works properly. I have no error handling simply because it is a little program for myself. But I'd like some suggestions about error handling. :)

Can you give me suggestions to improve the code? Maybe even to make it faster?

using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;

namespace ConsolePrimes
{
    public static class Program
    {
        public static void Main(string[] args)
        {
            Console.WriteLine("Up to which number shall all primes be calculated?");
            string inputvar = Console.ReadLine();
            ulong inputnumber = Convert.ToUInt64(inputvar);
            var primes = new List<ulong>();
            primes.Add(2);
            primes.Add(3);
            bool isprime = false;
            double result = 0;
            for (ulong i = 4; i<inputnumber; i++)
            {
                isprime = true;
                foreach (ulong prime in primes)
                {
                    result = i % prime;
                    if (result == 0)
                    {
                        isprime = false;
                        break;
                    }
                }
                if (isprime == true)
                {
                    primes.Add(i);
                }
            }
            int numberofprimes = primes.Count;
            Console.WriteLine("The Range from 0 to " + inputvar + " has " + Convert.ToString(numberofprimes) + " primes.");
            Console.WriteLine("The list of all primes is now getting exported to \"primes.txt\".");
            TextWriter tw = new StreamWriter("primes.txt");
            foreach (ulong nr in primes)
            {
               tw.WriteLine(nr);
            }
            tw.Close();
            Console.ReadLine();
        }
    }
}
up vote 11 down vote accepted

So this is a curious writeup, because primes can be calculated in many, many ways.

That said, there's one huge optimization we can use to cut your search pattern in half, and it starts here:

for (ulong i = 4; i<inputnumber; i++)
{

Fun fact: the only prime even number is 2, so we can actually rewrite this very quickly to remove half of the numbers you need to search:

for (ulong i = 5; i<inputnumber; i += 2)
{

Bam. Cut our search grid in half.

The next thing I would do is remove 2 from the List<ulong> of results, and we'll insert it later, because that will never match any of the values we're searching now:

var primes = new List<ulong>();
primes.Add(3);
...
primes.Insert(0, 2);

That way we get another speed boost, without sacrificing any of the rest of our code. (Are there better ways to do this? Sure.)


Next, we need to talk about some "best practices" and such:

Console.WriteLine("The Range from 0 to " + inputvar + " has " + Convert.ToString(numberofprimes) + " primes.");

This is something we call "string concatenation", basically, string1 + string2. It's frowned upon, and we recommend not doing it. Instead, use a formatted string, in one of two ways:

Console.WriteLine("The Range from 0 to {0} has {1} primes.", inputvar, numberofprimes);
Console.WriteLine($"The Range from 0 to {inputvar} has {numberofprimes} primes.");

Either will work, though the second is only supported in C# 6.0.


Next, there's one more huge optimization to make, and it's at this line:

double result = 0;

You don't realize it, but there's a boatload of casting/conversions here that shouldn't exist. Replace double with ulong and it goes away.

What's happening, is i % prime is a ulong, that is being casted to a double when assigned to result. This is an expensive operation, because the two types are stored in memory in completely different formats. Change the type, and you should get a 50%+ speed boost. (At least, I did.)


Additionally, you don't really need result, you don't use it for anything. So, I recommend removing it, and rewriting the foreach as follows:

for (ulong i = 5; i < inputnumber; i += 2)
{
    isprime = true;
    foreach (ulong prime in primes)
    {
        if (i % prime == 0UL)
        {
            isprime = false;
            break;
        }
    }
    if (isprime == true)
    {
        primes.Add(i);
    }
}

This gives you another speed boost, surprisingly.


Lastly, I recommend initializing the List with a default buffer. This should help avoid "resizing" that happens throughout the lifetime of the program. I used 500000, but as long as you use something reasonable (even 10000 is fine) it will give you a decent performance boost. (1-2%)


Overall, when we're done, the algorithm should look something like:

var primes = new List<ulong>(10000);
primes.Add(3);
bool isprime = false;
for (ulong i = 5; i < inputnumber; i += 2)
{
    isprime = true;
    foreach (ulong prime in primes)
    {
        if (i % prime == 0UL)
        {
            isprime = false;
            break;
        }
    }
    if (isprime == true)
    {
        primes.Add(i);
    }
}
primes.Insert(0, 2);
int numberofprimes = primes.Count;
  • Thanks a lot! I have tested it and actually it makes not much difference. In low numbers the new codes runs slower, in higher numbers (I tested 'til 1.000.000) it is a little faster (28146,8476ms compared to 28282,2768ms). Test it yourself if you don't believe me. ^^ – Kajkrow Aug 8 at 12:51
  • 1
    That sounds reasonable. You'll want to remember that most numbers are not prime, so you'll be iterating the entire primes list on almost every number, except those that are prime. (This is why prime calculation algorithms are notoriously slow.) – 202_accepted Aug 8 at 12:53
  • 1
    @Kajkrow Odd, mine dropped over 50%. What are you timing? I'm only timing the algorithm (at the very bottom). – 202_accepted Aug 8 at 13:17
  • 1
    Removing that double almost doubled the speed for me as well (pun intended). But a more significant improvement is to only check against primes up to the square root of i. – Pieter Witvoet Aug 8 at 15:24
  • 1
    @PieterWitvoet Aye, you should make that a new answer. ;) – 202_accepted Aug 8 at 15:27

Your problem statement is to find all primes up to a given input number. This just screams for a sieve-based solution. Now IF your problem statement was something like Project Euler Project 7, which is to find the 10001st prime number, then a prime generator similar to what you've posted would be the better fit.

A couple of things to keep in mind, particularly since you are new to C#. You need to find the right sized data type. UInt64 covers really big numbers. The problem is your solution required a List, which will cause memory issues before you get too far into the UInt32 numbers.

A more practical solution would be to scale your needs down to Int32 first. This not only uses less memory, but will be faster. Once you are happy there, then maybe step up to UInt32 and see how that goes.

I have already done such things with sieves from a hobbyist perspective. You are free to look at it to pick up any ideas.

Sieve31

Sieve32FastV2

Both of the above do not return a List, but rather an IEnumerable. It does keep a compressed internal list in memory, but not of numbers themselves but rather of bits associated with a numeric index. Besides memory concerns, keep in mind an array is limited to int.MaxValue items.

Other Code Comments

In addition to what @202_accepted wrote, I add:

You mix and match var and explicit type declarations. Actually, you only use var once. I'd suggest for consistency, you stick to one style.

You may simplify (isprime == true) to be (isprime).

A little whitespace for i<inputnumber becomes easier with i < inputnumber.

As your C# skills improve, you may find yourself breaking your app up into more modular pieces. Rather than having everything in Main(), you may find a cleaner organization of the code by having it: (1) perform data inputs and validation, (2) run primary method (i.e. generate list of primes), and finally (3) output to console and/or text file.

Maybe even to make it faster?

you don't need to do:

result % prime

for every prime in your list, it's enough to check every prime that is smaller then the square root of the number you're checking. So you can rewrite your code like this (eliminating useless conversions, as @202_accepted suggests, on the fly):

        for (ulong i = 4; i < inputnumber; i++)
        {
            isprime = true;
            ulong upperLimit = (ulong)(Math.Sqrt(i));

            foreach (ulong prime in primes)
            {
                if (prime > upperLimit)
                    break;

                if (i % prime == 0)
                {
                    isprime = false;
                    break;
                }
            }
            if (isprime == true)
            {
                primes.Add(i);
            }
        }

It works because every number n that is not prime fulfills one of the following:

  • it is a square number, in that case sqrt(n) is an integral value and gets checked by the code
  • it is a product of more then one prime. In this case, there is either a prime factor larger than sqrt(n) or it is not. If there is none, we're done. If there is one, there must also be one smaller then sqrt(n), otherwise n would be larger then itself, and we would've found that one by now.

This should give you a nice speed increase. On my machine, the Code went from "I'm to bored to wait" to about 300ms (for the primes <1000000).

For more speed you could just use int instead of ulong. Finding all primes for values larger then int.MaxValue is something you'll not see happening with that algorithm on a normal PC, unless you want to wait for ages.

After lots and lots of input (Thank you all!) I created this solution now. This is a improved code, that has a different approach to the problem. This code is limited to the first 2.000.000 numbers:

using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using System.Diagnostics;

namespace ConsolePrimes
{
    public static class Program
    {
        public static bool[] nonprimes = new bool[2000001];
        public static ulong i = 2;
        public static ulong inputnumber = 0;
        public static void Main(string[] args)
        {
            bool repeat = true;
            while (repeat)
            {
                Console.Clear();
                //Console.WriteLine("Up to which number shall all primes be calculated?");
                Console.WriteLine("Calculation until 2.000.000...");
                //string inputvar = Console.ReadLine();
                string inputvar = "2000000";
                Console.ReadLine();
                Stopwatch stopWatch = Stopwatch.StartNew();
                //inputnumber = Convert.ToUInt64(inputvar);
                inputnumber = 2000000;
                nonprimes[0] = true;
                nonprimes[1] = true;
                calcprime();
                i++;
                while ( i < inputnumber )
                {
                    calcprime();
                    i += 2;
                }
                List<ulong> primeoutput = new List<ulong>(1000000);
                ulong counter = 0;
                foreach (bool element in nonprimes)
                {
                    if (!(element))
                    {
                        primeoutput.Add(counter);
                    }
                    counter++;
                }
                stopWatch.Stop();
                Console.WriteLine("The Range from 0 to " + inputvar + " has " + Convert.ToString(primeoutput.Count) + " primes.");
                Console.WriteLine("The calculation took "+  Convert.ToString(stopWatch.Elapsed.TotalMilliseconds)  + "ms to be finished.");
                Console.WriteLine("The list of all primes is now getting exported to \"primes.txt\".");
                TextWriter tw = new StreamWriter("primes.txt");
                foreach (ulong nr in primeoutput)
                {
                   tw.WriteLine(nr);
                }
                tw.Close();
                Console.WriteLine("\nDo you want to start again?");
                string userinput = Console.ReadLine();
                string lowercaseinput = userinput.ToLower();
                if ( !(lowercaseinput.Equals("y")) )
                {
                    repeat = false;
                }
            }
        }
        public static void calcprime()
        {
            ulong k = 2;
            ulong j = i;
            ulong l = 0;
            while ( j*k <= inputnumber)
            {
                l = j*k;
                nonprimes[l] = true;
                k++;
            }
        }
    }
}

Now it takes around 50ms to calculate all primes until 2.000.000, previously it took over 20s to calculate until 1.000.000. So this is a huge improvement.

ATM I can only calculate primes until barely under 2.5 million. I will work on improving the code to go further.

  • You have presented an alternative solution, if you have done something in addition to the other answers then please explain in your answer so others can see how you made the code better. Code Review allows for Self Reviews of Code. – Malachi Aug 9 at 14:02
  • @Kajkrow Our CoC limits how we are allowed to comment on someone's answer. You are allowed to create a new question with this new code so that we may critique it more in-depth. If you choose to do that, please place a link back to this thread for reference. – Rick Davin Aug 10 at 12:13

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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