C# Program to Check Prime Number with Output and Explanation

You can check if a number is prime in C# by using a loop to test if it is divisible by any number from 2 up to its square root, for example: bool isPrime = true; for (int i = 2; i <= Math.Sqrt(n); i++) { if (n % i == 0) { isPrime = false; break; } }.

Examples

Input2

Output2 is a prime number.

Input15

Output15 is not a prime number.

Input1

Output1 is not a prime number.

How to Think About It

To check if a number is prime, think about whether it can be divided evenly by any number other than 1 and itself. Start checking from 2 up to the square root of the number because if it has a factor larger than its square root, the corresponding smaller factor would have been found already. If no divisors are found, the number is prime.

Algorithm

1

Get the input number.

2

If the number is less than 2, it is not prime.

3

Check divisibility from 2 up to the square root of the number.

4

If any divisor divides the number evenly, it is not prime.

5

If no divisors are found, the number is prime.

6

Return or print the result.

Code

csharp

using System;
class Program {
    static void Main() {
        int n = 17;
        bool isPrime = true;
        if (n < 2) isPrime = false;
        else {
            for (int i = 2; i <= Math.Sqrt(n); i++) {
                if (n % i == 0) {
                    isPrime = false;
                    break;
                }
            }
        }
        Console.WriteLine(isPrime ? $"{n} is a prime number." : $"{n} is not a prime number.");
    }
}

Output

17 is a prime number.

Dry Run

Let's trace the number 17 through the code to see how it checks for prime.

1

Initialize

n = 17, isPrime = true

2

Check if less than 2

17 is not less than 2, continue

3

Loop from 2 to sqrt(17)

Check i = 2, 3, 4

4

Check divisibility

17 % 2 != 0, 17 % 3 != 0, 17 % 4 != 0

5

No divisors found

isPrime remains true

6

Print result

"17 is a prime number."

i	n % i	isPrime
2	1	true
3	2	true
4	1	true

Why This Works

Step 1: Start with assumption

We assume the number is prime by setting isPrime = true.

Step 2: Check small numbers

Numbers less than 2 are not prime, so we set isPrime = false immediately.

Step 3: Test divisors up to square root

We only check divisors up to Math.Sqrt(n) because larger factors would have smaller pairs already checked.

Step 4: Update prime status

If any divisor divides the number evenly (n % i == 0), we set isPrime = false and stop checking.

Alternative Approaches

Check divisibility up to n-1

csharp

using System;
class Program {
    static void Main() {
        int n = 17;
        bool isPrime = true;
        if (n < 2) isPrime = false;
        else {
            for (int i = 2; i < n; i++) {
                if (n % i == 0) {
                    isPrime = false;
                    break;
                }
            }
        }
        Console.WriteLine(isPrime ? $"{n} is a prime number." : $"{n} is not a prime number.");
    }
}

Simpler but slower because it checks more numbers than needed.

Use a function with early return

csharp

using System;
class Program {
    static bool IsPrime(int n) {
        if (n < 2) return false;
        for (int i = 2; i <= Math.Sqrt(n); i++) {
            if (n % i == 0) return false;
        }
        return true;
    }
    static void Main() {
        int n = 17;
        Console.WriteLine(IsPrime(n) ? $"{n} is a prime number." : $"{n} is not a prime number.");
    }
}

Cleaner code by separating logic into a function.

Complexity: O(√n) time, O(1) space

Time Complexity

The loop runs up to the square root of n, so the time grows roughly with √n.

Space Complexity

Only a few variables are used, so space is constant O(1).

Which Approach is Fastest?

Checking up to the square root is faster than checking all numbers up to n-1.

Approach	Time	Space	Best For
Check up to sqrt(n)	O(√n)	O(1)	Efficient prime check
Check up to n-1	O(n)	O(1)	Simple but slower
Function with early return	O(√n)	O(1)	Clean and reusable code