Check if number is Prime – C# Method

Prime number or Prime is a number greater than 1 that can be divided only by 1 and itself. In other words, it can’t be formed by multiplying two other numbers. The first ten prime numbers are: 2, 3, 5, 7, 11, 13, 17, 19, 23 and 29. 2 is the only even number that is prime. There are several ways to check for prime numbers and in some cases a brute force algorithm might not be a problem. If the system has restrictions or you are trying to solve a programming challenge with time restrictions then you need an algorithm that can find the answer fast. The method provided is simple and fast and used in many programming challenges with time restrictions.

public static bool IsPrime(long candidate)
{
    if ((candidate & 1) == 0)
    {
        return candidate == 2;
    }

    for (long i = 3; i * i <= candidate; i += 2)
    {
        if (candidate % i == 0)
        {
            return false;
        }
    }

    return candidate != 1;
}

The first check might not very clear and you can use modulo 2 instead but basically it checks if the number is even. If the number is even the method returns true if the candidate is 2 and false otherwise. For the second part, we check all odd numbers starting from 3 until the square root of the number if they divide the candidate without remainder. The reason we check until the square root of the number is because if we didn’t find a divisor until that point, it means there is not any.