LINQ Expression to Test If a Number is Prime

by Zoran Horvat
December 14, 2014

Suppose that we want to test whether a given integer number greater than one is prime. We can accomplish that with a simple for loop:

int number = 719;

bool isPrime = true;
for (int divisor = 2; divisor <= Math.Sqrt(number); divisor++)
    if (number % divisor == 0)
    {
        isPrime = false;
        break;
    }

Console.WriteLine("Number {0} is {1}prime.", number, isPrime ? "" : "not ");

This loop works fine and it really detects that 719 is a prime number.

The same effect can be accomplished with LINQ. Here is the LINQ expression which returns exactly the same result as the previous loop:

bool isPrime =
    Enumerable.Range(2, (int)Math.Sqrt(number) - 1)
    .All(divisor => number % divisor != 0);

This simple expression iterates through numbers up to the square root of the tested value and tries to divide the value with each of the numbers in the range. Loop exits when the first divisor is detected and subsequent divisions are not performed. This guarantees optimal execution of the expression.