Prime Number Program in C#: Check, List and Sieve Primes

Is 97 prime? A prime number program in C# answers that by trying divisors: return false below 2, return n == 2 for even numbers, then test odd divisors while i <= n / i. If none divides evenly, it’s prime.

In this tutorial, I’ll grow one small PrimeTools class step by step, the way you’d write a prime number program in C#: a basic check, a fast IsPrime, a range, an array, a sieve and 64-bit values.

It’s the version I’d want to see in an interview or a CS course. Each step is a .NET 10 file you can run with dotnet run, with its real output under it.

What Counts as a Prime Number?

A prime is a whole number greater than 1 whose only divisors are 1 and itself. So 1 isn’t prime, 0 and negatives aren’t either, and 2 is the only even prime.

Every method below starts from those rules. Like the Armstrong number program in C#, it’s a small exercise that interviewers use to see how you handle edge cases.

Step 1: Check a Prime Number in C# with a Simple Loop

The first version tries every divisor from 2 to n – 1. I also added the LINQ one-liner you’ll see in older answers, Enumerable.Range(2, n - 2).All(...), so you can compare them:

int[] tests = [1, 2, 9, 17, 25, 29, 97];
foreach (int n in tests)
    Console.WriteLine($"{n,3} -> loop: {PrimeTools.IsPrimeNaive(n),-5}  LINQ: {PrimeTools.IsPrimeLinq(n)}");

static class PrimeTools
{
    // Step 1: try every divisor from 2 to n - 1
    public static bool IsPrimeNaive(int n)
    {
        if (n < 2) return false;          // 0, 1 and negatives aren't prime
        for (int i = 2; i < n; i++)
            if (n % i == 0) return false; // found a divisor
        return true;
    }

    // Same idea as a one-liner
    public static bool IsPrimeLinq(int n) =>
        n > 1 && Enumerable.Range(2, n - 2).All(d => n % d != 0);
}

Output:

  1 -> loop: False  LINQ: False
  2 -> loop: True   LINQ: True
  9 -> loop: False  LINQ: False
 17 -> loop: True   LINQ: True
 25 -> loop: False  LINQ: False
 29 -> loop: True   LINQ: True
 97 -> loop: True   LINQ: True

Both agree, but for a large prime they run almost n times. If the loop syntax is new to you, my guide to the for loop in C# covers it.

Step 2: Faster C# IsPrime Method with the Square Root

Divisors come in pairs. If 7919 had a factor above its square root, it would also have one below it, so you can stop at the square root and skip even numbers after 2. I wrote that loop two ways:

foreach (int n in new[] { 2, 4, 97, 7919, int.MaxValue })
    Console.WriteLine($"{n,10}  i*i: {PrimeTools.IsPrimeSquared(n),-5}  n/i: {PrimeTools.IsPrime(n)}");

static class PrimeTools
{
    public static bool IsPrimeSquared(int n)
    {
        if (n < 2 || n % 2 == 0) return n == 2;
        for (int i = 3; i * i <= n; i += 2)
            if (n % i == 0) return false;
        return true;
    }

    public static bool IsPrime(int n)
    {
        if (n < 2 || n % 2 == 0) return n == 2;
        for (int i = 3; i <= n / i; i += 2)   // can't overflow
            if (n % i == 0) return false;
        return true;
    }
}

Output:

         2  i*i: True   n/i: True
         4  i*i: False  n/i: False
        97  i*i: True   n/i: True
      7919  i*i: True   n/i: True
2147483647  i*i: False  n/i: True

Look at the last row. int.MaxValue is a prime, yet the common i * i <= n loop says false. Once i passes 46,340, i * i overflows, the condition never fails, and the loop eventually tries n itself.

Writing it as i <= n / i tests the same thing without overflow. That’s why it’s the version the rest of this post keeps.

IsPrime is a static method that returns bool, so you can call it anywhere without an object. I explain that pattern in functions in C#.

Step 3: Print All Prime Numbers from 1 to 100 in C#

With IsPrime done, a range is just a loop that keeps the numbers that pass. I also added NthPrime, which counts up until it has seen the nth prime:

List<int> primes = [];
for (int n = 1; n <= 100; n++)
    if (PrimeTools.IsPrime(n)) primes.Add(n);

Console.WriteLine(string.Join(" ", primes));
Console.WriteLine($"Primes from 1 to 100: {primes.Count}");
Console.WriteLine($"10th prime: {PrimeTools.NthPrime(10)}");
Console.WriteLine($"100th prime: {PrimeTools.NthPrime(100)}");

static class PrimeTools
{
    // Step 3: count primes until we reach the nth one
    public static int NthPrime(int nth)
    {
        int count = 0, n = 1;
        while (count < nth)
            if (IsPrime(++n)) count++;
        return n;
    }

    public static bool IsPrime(int n)
    {
        if (n < 2 || n % 2 == 0) return n == 2;
        for (int i = 3; i <= n / i; i += 2)
            if (n % i == 0) return false;
        return true;
    }
}

Output:

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
Primes from 1 to 100: 25
10th prime: 29
100th prime: 541

There are 25 primes between 1 and 100, from 2 up to 97, a handy sanity check for any version you write.

NthPrime uses a while loop because you don’t know in advance how far it’ll go. See the while loop in C# if you want the details.

Step 4: Find Prime Numbers in an Array or List with LINQ

Because IsPrime takes an int and returns a bool, you can pass it straight to LINQ as a method group. Here I filter units per order from a Dallas warehouse shift:

// Units per order on one Dallas warehouse shift
int[] units = [12, 17, 23, 30, 31, 45, 53, 64, 89, 91, 97, 1];

int[] primes = units.Where(PrimeTools.IsPrime).ToArray();
Console.WriteLine($"Prime quantities: {string.Join(", ", primes)}");
Console.WriteLine($"How many: {units.Count(PrimeTools.IsPrime)}");
Console.WriteLine($"Largest: {primes.Max()}");

List<int> boxes = [4, 6, 8, 9];
Console.WriteLine($"Any prime in the list? {boxes.Any(PrimeTools.IsPrime)}");

static class PrimeTools
{
    public static bool IsPrime(int n)
    {
        if (n < 2 || n % 2 == 0) return n == 2;
        for (int i = 3; i <= n / i; i += 2)
            if (n % i == 0) return false;
        return true;
    }
}

Output:

Prime quantities: 17, 23, 31, 53, 89, 97
How many: 6
Largest: 97
Any prime in the list? False

Where(PrimeTools.IsPrime) keeps 17, 23, 31, 53, 89 and 97. It correctly drops 91, which looks prime but is 7 x 13, and 1. The same calls work on a List<int>.

For more on declaring and looping through arrays, read my complete guide to C# arrays.

Step 5: Sieve of Eratosthenes for All Primes up to 1,000,000

Calling IsPrime on every number repeats a lot of work. The sieve crosses out multiples of each prime instead, starting at i * i, and whatever’s left is prime:

bool[] composite = PrimeTools.Sieve(1_000_000);
int count = 0, last = 0;
for (int n = 2; n < composite.Length; n++)
    if (!composite[n]) { count++; last = n; }

Console.WriteLine($"Primes up to 1,000,000: {count}");
Console.WriteLine($"Largest one: {last}");

static class PrimeTools
{
    // Step 5: Sieve of Eratosthenes (true = crossed out)
    public static bool[] Sieve(int limit)
    {
        var composite = new bool[limit + 1];
        for (int i = 2; i <= limit / i; i++)
            if (!composite[i])
                for (int j = i * i; j <= limit; j += i)
                    composite[j] = true;
        return composite;
    }
}

Output:

Primes up to 1,000,000: 78498
Largest one: 999983

It found 78,498 primes up to one million, the largest being 999,983. I also checked every one of them against IsPrime, and they matched.

On my laptop the sieve finished instantly, while checking a million numbers one by one was noticeably slower. Use it when you need many primes in a range, much like you’d loop once to find the sum of the first n numbers in C#.

Step 6: Check if a long or BigInteger Number Is Prime in C#

For values past int.MaxValue, switch the types to long. I also added the Fermat shortcut from the old version of this post, built on BigInteger.ModPow:

using System.Numerics;

foreach (long n in new long[] { 561, 999999999989, long.MaxValue })
    Console.WriteLine($"{n,19}  Fermat: {PrimeTools.Fermat(n),-5}  IsPrime: {PrimeTools.IsPrime(n)}");

static class PrimeTools
{
    // Step 6: same trial division, now on long
    public static bool IsPrime(long n)
    {
        if (n < 2 || n % 2 == 0) return n == 2;
        for (long i = 3; i <= n / i; i += 2)
            if (n % i == 0) return false;
        return true;
    }

    // Fermat shortcut: fast, but fooled by Carmichael numbers like 561
    public static bool Fermat(long n) => BigInteger.ModPow(2, n - 1, n) == 1;
}

Output:

                561  Fermat: True   IsPrime: False
       999999999989  Fermat: True   IsPrime: True
9223372036854775807  Fermat: False  IsPrime: False

Fermat calls 561 prime, but it’s 3 x 11 x 17, a Carmichael number. Trial division gets all three right, though a 19-digit prime would take billions of divisions.

BigInteger has no built-in primality test in .NET 10, so for huge values you’d implement Miller-Rabin with ModPow. Big values grow fast, as you’ll also see in the factorial program in C#.

Which Prime Number Method in C# Should You Use?

You need	Use	Result from my runs
Is one int prime?	IsPrime with i <= n / i	int.MaxValue -> True
Primes in a small range	a loop over IsPrime	25 primes from 1 to 100
Primes in an array or list	Where(PrimeTools.IsPrime)	17, 23, 31, 53, 89, 97
Every prime up to a limit	Sieve of Eratosthenes	78,498 up to 1,000,000
A long value	IsPrime(long); Miller-Rabin for huge ones	561 -> False

If you’re practicing for interviews, these number programs pair well with this one:

Frequently Asked Questions