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

Answer 1

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