LESSON 133 OF 338 · LOOPS & CONDITIONALS

Prime Number in Go: O(n) Trial Division

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

Prime Number in Go, explained

Problem overview

The function isPrime receives a non-negative integer n and returns true if it is prime and false if it is not. A prime is a number greater than 1 whose only divisors are 1 and itself. So 31 is prime, while 6 is not, because 2 and 3 divide it. The numbers 0 and 1 are not prime by definition.

The statement asks for O(n) time and O(1) extra space, so a loop that tries every candidate divisor once is enough.

Approach: look for a divisor between 2 and n - 1

Turn the definition around. A number n is prime exactly when it is at least 2 and no number d with 1 < d < n divides it. That gives a direct algorithm: try each d from 2 up to n - 1, and the moment one divides n evenly, return false. If none does, return true.

The divisibility test is the remainder operator: n % d == 0 means d goes into n with nothing left over. For n = 6, the first candidate is 2, and 6 % 2 is 0, so the loop returns false immediately. For n = 31, no candidate from 2 to 30 gives a remainder of 0, so the loop ends and the function returns true.

This is trial division in its simplest form. It does more work than needed: a divisor larger than the square root of n always pairs with a smaller one, so stopping at the square root would be faster. This lesson keeps the simple version, which fits the stated O(n) budget.

Step by step

Handle the small numbers first. If n < 2, return false. This covers 0 and 1, which have no place among the primes. Without this check, the loop would not run for them and the function would wrongly return true.
Loop over candidate divisors. Declare d with := in a for loop, start it at 2, and stop before n. A prime always divides itself, and 1 always divides it, so those two are excluded.
Test each candidate. If n % d == 0, then n has a divisor other than 1 and itself, so return false at once.
Return true after the loop. Reaching this line means the loop checked every candidate and found no divisor.

The solution in Go

func isPrime(n int) bool {
    if n < 2 {
        return false
    }
    for d := 2; d < n; d++ {
        if n % d == 0 {
            return false
        }
    }
    return true
}

Go details to know:

The three-part for. for d := 2; d < n; d++ has an initialiser, a condition and a step, separated by semicolons and with no parentheses. The variable d exists only inside the loop.
% on integers. The result takes the sign of the left operand. That doesn't matter here, because n is non-negative and d is positive, but it would matter for negative inputs.
Every path returns. The final return true is required. Without it, Go reports missing return, since the loop might finish.
int is 64 bits in Go 1.22 on a 64-bit machine, so the loop counter doesn't overflow for any realistic input.

Complexity

Time: O(n). For a prime, the loop runs n - 2 times, once for each d from 2 to n - 1. For a composite number it stops at its smallest divisor, which is often much earlier. An even number above 2 ends at d = 2.

Space: O(1). Only d and n are used.

Edge cases and common mistakes

0 and 1. Both return false from the first check. Leaving that check out would make isPrime(1) return true.
2. It is the smallest prime. The loop starts at 2 and needs d < 2, so it doesn't run, and the function returns true.
Starting the loop at 1. Every number is divisible by 1, so every input would give false.
Ending the loop at d <= n. Every n is divisible by itself, so that would also reject every prime.
Returning inside the loop too early. Writing else { return true } makes the first candidate decide the answer, which is wrong: 9 is not divisible by 2 but is divisible by 3.
Perfect squares of primes. 9 and 25 are not prime. A loop that stops too early at the square root (with < instead of <=) misses them.

Testing

isPrime(31) gives true.
isPrime(6) gives false.
isPrime(0) and isPrime(1) give false.
isPrime(2) gives true.
isPrime(9) gives false.
isPrime(97) gives true.

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

Start learning free