Start learning free

LESSON 132 OF 347 · LOOPS & CONDITIONALS

Prime Number in C#: O(n) Trial Division

Practice Read the full explanation

Given a non-negative integer n check if it is a prime number

Prime numbers are positive numbers greater than 1 that are divisible only by 1 and the number itself.

Examples of prime numbers: 2, 3, 5, 7, 11, 13, 17, 19, 23

Example 1:

Input: n = 31
Output: true

Example 2:

Input: n = 6
Output: false
Explanation: 6 is divisible by 2 and 3.

Note:

Your algorithm should run in O(n) time and use O(1) space.

Hints:

Prime numbers are only divisible by the number 1 or itself. Let's reformulate this definition a little bit:
A number n is prime if and only if there is no such number d such that 1 < d < n and d is a divisor of n. Is this new definition more helpful?

We should iterate through each number d from 2 to n - 1 and check if d is a divisor of n.
If we find such a number, we can conclude that n is not prime and return false right away:

for each d : 2 -> n - 1:
	if d is divisor of n:
		return false

How do we check if d is divisor of n? When should we return true?

d is divisor of n (or n is a multiple of d) if and only if n % d == 0:

for each d : 2 -> n - 1:
	if n % d == 0:
		return false
return true

As you can see, if the for loop terminates and we reach the return true line of code, we know that we haven't found a divisor, so it's safe to say n is prime.

We have a for loop that performs exactly n - 2 iterations, thus the Time Complexity is O(n).
The only extra space we use is the iterator variable i inside the loop, thus the Extra Space used is O(1).

STEP 1 OF 4

Guided

Ctrl + Enter to check

C# · LOOPS & CONDITIONALS

Prime Number in C#, explained

Problem overview

The method IsPrime(int n) returns true when n is a prime number and false otherwise. A prime is an integer greater than 1 whose only divisors are 1 and itself. So 31 is prime, 6 is not (it is divisible by 2 and 3), and neither 0 nor 1 is prime.

The statement sets a budget of O(n) time and O(1) extra space. That is generous enough for the direct approach: try every candidate divisor.

Approach: look for a divisor

A number n is prime exactly when no number d with 1 < d < n divides it. That turns the definition into a search: try each d from 2 up to n - 1, and if any one divides n evenly, n is not prime and the method can answer false immediately. If no d divides n, it is prime.

A number d divides n exactly when the remainder n % d is 0. For 6, the remainder with 2 is 0, so the search stops at the first candidate. For 31, none of 2 to 30 gives remainder 0, so the loop runs to the end.

The search needs to be guarded against small inputs. The definition says primes are greater than 1, but a loop from 2 to n - 1 would not run at all for 0 and 1, and the method would fall through to true. Those numbers are not prime, so they must be handled before the loop.

Step by step

Reject numbers below 2. If n < 2, return false. This covers 0 and 1.
Loop over the candidates. Declare int d = 2 and loop while d < n, increasing d by one each time. The upper limit leaves out n itself, which divides everything trivially.
Test for a divisor. If n % d == 0, return false. One divisor is enough to rule n out.
Return true after the loop. If the loop ended, no divisor exists.

The solution in C#

class Solution {
    public bool IsPrime(int n) {
        if (n < 2) {
            return false;
        }
        for (int d = 2; d < n; d++) {
            if (n % d == 0) {
                return false;
            }
        }
        return true;
    }
}

Some C# details:

The remainder operator % gives the remainder of integer division, so 31 % 2 is 1 and 6 % 3 is 0.
The name is IsPrime, with a bool return type and lowercase true and false.
The loop starts at 2 and uses d < n. For n = 2, the loop condition is false at once, so the loop body never runs and the method returns true. That is correct, since 2 is prime.
Each path returns a value. The compiler checks that, and the final return true; covers the loop finishing.

Tracing 9 and 13

For n = 9: d = 2 gives remainder 1, so the loop continues. d = 3 gives remainder 0, so the method returns false and never tries 4 to 8. For n = 13, every d from 2 to 12 leaves a non-zero remainder, the loop ends, and the method returns true. The two traces show the two ways out of the method: early from inside the loop, or at the end after it.

Complexity

Time: O(n). The loop makes at most n - 2 iterations, each doing one remainder operation. For a composite number the loop usually stops much earlier, at its smallest divisor, but a prime forces the full run.

Space: O(1). The method uses only d.

This is the simplest correct approach, not the fastest one. Any divisor of n larger than its square root is paired with one smaller than it, so checking up to the square root would be enough. That brings the time to O(sqrt(n)), but this lesson stays with the full range.

Edge cases and common mistakes

0 and 1. Both are not prime. Without the first if, they would pass through the loop untouched and be reported as prime.
2. The smallest prime. It works because the loop body never runs.
Starting the loop at 1. Every number is divisible by 1, so the method would return false for everything.
Using d <= n. Every number is divisible by itself, so again every input would be reported as not prime.
Returning true inside the loop. If you write else { return true; } next to the test, the method decides after checking only d = 2. 9 would be reported as prime. The answer true is only safe after every candidate has been tried.
Large inputs. A big prime such as 2147483647, the largest int, makes the loop run about two billion times, which is slow. The lesson's tests use modest values.

Why the guard comes first

Placing the n < 2 check before the loop keeps the loop simple. The loop only has to reason about numbers that are at least 2, where "has a divisor between 2 and n - 1" is exactly the same as "is not prime". Folding the special cases into the loop would make the loop harder to read and easier to get wrong.

Testing

31 gives true.
6 gives false.
2 gives true, and 3 gives true.
1 and 0 both give false.
9 gives false, and 25 gives false: squares of primes are a good test for the loop.

Keep going with C#About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free