Calculating primes until a user-given value

Question

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();
        }
    }
}

Answer 1

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;

Answer 2

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.

Answer 3

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.

Answer 4

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.