2
\$\begingroup\$

I have just started learning C# and decided to do some problems from Project Euler. I wrote a code to find 10 001st prime and I thought it would be cool optimize it to make it as fast as possible. How could I improve this to make it even faster?

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Diagnostics;

namespace primes
{
    class Program
    {
        static void Main(string[] args)
        {
            long prime = 2;
            long largestprime = 2;
            long potentialprime = 3;
            Console.WriteLine("Enter the prime you want to find: ");
            long primenum = Convert.ToInt64(Console.ReadLine());
            long[] primearray = new long[primenum + 1];
            primearray[1] = 2;
            Stopwatch sw = new Stopwatch();
            sw.Start();
            while (prime <= primenum)
            {
                bool isprime = true;
                for (long x = 1; x < prime; x += 3)
                {
                    if (primearray[x] * primearray[x] > potentialprime)
                         break;
                    if (prime > 3 && (potentialprime % primearray[x] == 0 || potentialprime % primearray[x+1] == 0 || potentialprime % primearray[x+2] == 0))
                         isprime = false;
                    if (prime <= 3 && potentialprime % primearray[x] == 0)
                         isprime = false;

                 }
                 if (isprime)
                {
                    primearray[prime] = potentialprime;
                    prime += 1;
                    largestprime = potentialprime;
                }
                potentialprime += 2;
            }
            sw.Stop();
            Console.WriteLine(sw.ElapsedMilliseconds + "ms to find ");
            Console.WriteLine(largestprime);
            Console.ReadKey();
         }
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ You might want to take a look at the answers of my question. \$\endgroup\$ – Denis Jul 18 '18 at 8:06
  • 2
    \$\begingroup\$ Shouldn't this code calculate the 10.001st prime? I don't think it does. \$\endgroup\$ – t3chb0t Jul 18 '18 at 11:03
  • \$\begingroup\$ I changed it so it can calculate nth number prime where n is taken as an input \$\endgroup\$ – Naia Suzuki Jul 18 '18 at 11:28
  • 1
    \$\begingroup\$ I would focus on increasing readability, maybe you will then spot the answer to your question by yourself. \$\endgroup\$ – Slampen Jul 19 '18 at 7:16
  • 1
    \$\begingroup\$ This is Project Euler Problem 7 for those who want the link. \$\endgroup\$ – rossum Jul 29 '18 at 12:19
2
\$\begingroup\$

As mentioned in the comments, you should go for more readable code:

1) Split by responsibility:

One method for user input:

ulong GetPrimeIndex() { // TODO: Get User input from Console }

The algorithm itself:

ulong FindNthPrime(ulong n) { // TODO: the algorithm }

print the result...

public static void Main(string[] args)
{ 
  ulong primeIndex = GetPrimeIndex();

  Stopwatch watch = Stopwatch.StartNew();
  ulong nthPrime = FindNthPrime(primeIndex);
  watch.Stop();

  Console.WriteLine($"{primeIndex} prime is: {nthPrime}");
  Console.WriteLine($"Elapsed time: {watch.ElapsedMilliseconds}");
}

2) Naming:

In C# local variable names use camelCase: largestprime should be largestPrime


Because primes are always positive, you should use ulong instead of long. It will give you a broader range to operate in.


I think you're missing a couple of breaks in these tests:

                if (primearray[x] * primearray[x] > potentialprime)
                     break;
                if (prime > 3 && (potentialprime % primearray[x] == 0 || potentialprime % primearray[x+1] == 0 || potentialprime % primearray[x+2] == 0))
                     isprime = false;
                if (prime <= 3 && potentialprime % primearray[x] == 0)
                     isprime = false;

It should be:

  if (primearray[x] * primearray[x] > potentialprime)
    break;
  if (prime > 3 && (potentialprime % primearray[x] == 0 || potentialprime % primearray[x + 1] == 0 || potentialprime % primearray[x + 2] == 0))
  {
    isprime = false;
    break;
  }
  if (prime <= 3 && potentialprime % primearray[x] == 0)
  {
    isprime = false;
    break;
  }

Be aware that

primearray[x] * primearray[x]

may overflow the domain range. You should maybe make the check by sqrt instead?

\$\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.