Check if a number is prime in C#

Question

the following code works but for some numbers it needs a lot of time to say if the number is prime or not. What can i do to make it faster? Here is the code:

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

namespace Exercise23
{
    class Exercise23
    {
        static void Main(string[] args)
        {
            long number = long.Parse(Console.ReadLine());
            if (IsPrime(number))
            {
                Console.WriteLine("True");
            }
            else
            {
                Console.WriteLine("False");
            }
        }
        public static bool IsPrime(long number)
        {
            if (number == 1) return false;
            if (number == 2) return true;
            //if (number == 6737626471) return true;

            if (number % 2 == 0) return false;    

            for (int i = 3; i < number; i += 2)
            {
                if (number % i == 0) return false;
            }
            return true;
        }
    }
}

Some algorithms just take a long time depending on the inputs, and that's just the way it is. Think about the super computers that compute the many digits of pi which still take a lot of time. — rory.ap, May 20 '16 at 14:45
This is one of the slowest algorithms for determining primeness. The first step to make this faster: you only have to iterate to the square root of `number` (higher values can't be divisors). — René Vogt, May 20 '16 at 14:46
@RenéVogt - higher values can be divisors - but if there is one, you'll have already located at least one other divisor (by which the higher divisor can be multiplied to obtain the original number) E.g. sqrt(10) is 3.16. Are you going to claim that 5 isn't a divisor of 10? — Damien_The_Unbeliever, May 20 '16 at 14:48
This is one of the most classic problem of math (particularly number theory) and computing... the solution can be very simple to very complex, and the performance is varying a lot. It is quite broad topic, so to say... — Ian, May 20 '16 at 14:48
Probably *the* slowest way. There is no reason to check for numbers greater than`number/2`. — Panagiotis Kanavos, May 20 '16 at 14:50
If this code works as is and the desire is simply to make it faster, doesn't it belong on CodeReview? — Chris Dunaway, May 20 '16 at 15:43

Dmitry Bychenko · Accepted Answer · 2016-05-20T15:01:01.873

5

An easiest improvement is to make the loop shorter. If number is not prime, it can be written as

  N = A * B

Let A <= B; in the worst case (A == B) and so A <= sqrt(N).

  public static bool IsPrime(long number) {
    if (number <= 1)
      return false;
    else if (number % 2 == 0)
      return number == 2;

    long N = (long) (Math.Sqrt(number) + 0.5);

    for (int i = 3; i <= N; i += 2)
      if (number % i == 0)
        return false; 

    return true;
  }

So you have O(sqrt(N)) algorithm instead of O(N). For real improvement (for big numbers) see

AKS test (primarily academic use)

https://en.wikipedia.org/wiki/AKS_primality_test

Rabin-Miller test

https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test

edited May 20 '16 at 15:01

answered May 20 '16 at 14:55

Dmitry Bychenko

180,369
20
160
215

1

This can be written as `for (int i = 3; i * i <= number; i += 2)` without calculating `sqrt` – Phate01 May 20 '16 at 14:57
1

@Phate01: technically, you're right; but `sqrt` computed just *once*, while multiplication performs at *each iteration*. – Dmitry Bychenko May 20 '16 at 14:59
I just realized that performance issue :D – Phate01 May 20 '16 at 15:00
Yes this is the most effective way to check if a number is prime without running into performance issues based on the big O notation. Reducing the number of loops in any given code makes it faster. I used to be a Euclidian Sieve prime checker fan but now I like this new method of checkinf for primes. – Son of Man Jun 18 '23 at 07:14

score 4 · Answer 2 · edited May 23 '17 at 11:44

Based on this answer: https://stackoverflow.com/a/26760082/4499267 a way to speed things up can be:

The algorithm can be improved further by observing that all primes are of the form 6k ± 1, with the exception of 2 and 3.
This is because all integers can be expressed as (6k + i) for some integer k and for i = −1, 0, 1, 2, 3, or 4; 2 divides (6k + 0), (6k + 2), (6k + 4); and 3 divides (6k + 3).
So a more efficient method is to test if n is divisible by 2 or 3, then to check through all the numbers of form 6k ± 1 ≤ √n.
This is 3 times as fast as testing all m up to √n.

Here's a C implementation

int IsPrime(unsigned int number) {
    if (number <= 3 && number > 1) 
        return 1;            // as 2 and 3 are prime
    else if (number == 1 || number%2==0 || number%3==0) 
        return 0;     // check if number is divisible by 2 or 3
    else {
        unsigned int i;
        for (i=5; i*i<=number; i+=6) {
            if (number % i == 0 || number%(i + 2) == 0) 
                return 0;
        }
        return 1; 
    }
}

Check if a number is prime in C#

2 Answers2