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\$
5
  • 1
    \$\begingroup\$ You might want to take a look at the answers of my question. \$\endgroup\$
    – Denis
    Jul 18, 2018 at 8:06
  • 2
    \$\begingroup\$ Shouldn't this code calculate the 10.001st prime? I don't think it does. \$\endgroup\$
    – t3chb0t
    Jul 18, 2018 at 11:03
  • \$\begingroup\$ I changed it so it can calculate nth number prime where n is taken as an input \$\endgroup\$ Jul 18, 2018 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, 2018 at 7:16
  • 1
    \$\begingroup\$ This is Project Euler Problem 7 for those who want the link. \$\endgroup\$
    – rossum
    Jul 29, 2018 at 12:19

1 Answer 1

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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