Start learning free

LESSON 138 OF 415 · LOOPS & CONDITIONALS

Prime Number in Swift: O(n) Trial Division with a for Loop

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 d inside the loop, thus the Extra Space used is O(1).

STEP 1 OF 4

Guided

Ctrl + Enter to check

SWIFT · LOOPS & CONDITIONALS

Prime Number in Swift, explained

Problem overview

The method isPrime takes a non-negative integer n and returns true if it is prime. A prime is greater than 1 and divisible only by 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.

The statement asks for O(n) time and O(1) extra space.

Approach: look for a divisor

A number n is prime exactly when no number d with 1 < d < n divides it. That turns the problem into a search for a counterexample. Try every d from 2 up to n - 1. The first one that divides n proves n is not prime, so the method returns false at once. If none divides it, the method returns true.

This is called trial division. It performs about n - 2 checks, which fits the O(n) budget. Faster versions exist, but this lesson uses the direct one.

A number d divides n when the remainder n % d is 0.

Worked examples

For n = 6 the loop tries 2 first. The remainder 6 % 2 is 0, so 2 divides 6 and the method returns false without trying 3, 4 or 5. For n = 7 the loop tries 2, 3, 4, 5 and 6, and every remainder is non-zero. The loop ends, and the method reaches return true.

The asymmetry matters again: a single divisor is enough to say "not prime", but "prime" can only be claimed after every candidate has been ruled out.

Step by step

Reject numbers below 2. 0 and 1 are not prime, so if n < 2 returns false. This must come first, and the next step shows why it matters in Swift.
Loop over the candidate divisors with for divisor in 2..<n, a half-open range that includes 2 and stops before n.
Test divisibility. If n % divisor == 0, return false.
Return true after the loop. No divisor was found.

The solution in Swift

class Solution {
    func isPrime(_ n: Int) -> Bool {
        if n < 2 {
            return false
        }
        for divisor in 2..<n {
            if n % divisor == 0 {
                return false
            }
        }
        return true
    }
}

Swift details worth knowing:

Ranges must not run backwards. 2..<n is valid when n is 2 or more. For n = 2 the range is empty, the loop doesn't run, and 2 is correctly reported as prime. For n = 1 the range 2..<1 would have its upper bound below its lower bound, and a range like that makes the program crash at run time. That is exactly why the check for n < 2 comes first.
The loop variable is a constant that Swift creates for each pass, so divisor needs no declaration.
Early return. A return inside the loop leaves the method immediately.
Remainder. % works on Int values. Because n is non-negative here, the sign rules for negative remainders don't come into play.

Complexity

Time: O(n). For a prime, the loop runs through all n - 2 candidates. For a composite number the method stops at its smallest divisor, which is often much sooner.

Space: O(1). Only the loop variable is used.

It is enough to try divisors up to the square root of n, because a divisor larger than that is paired with a smaller one. That version, written as while d * d <= n, runs in O(sqrt(n)) time. It gives the same answers, for example true for 97 and false for 91.

Why the loop can be shortened

Divisors of a composite number come in pairs: if d divides n, so does n / d, and one of the two is never larger than the square root of n. For 91 the pair is 7 and 13. So if no divisor is found up to the square root, none exists beyond it either. In Swift the shortened loop is easiest to write with var d = 2 and while d * d <= n, increasing d by one at the end of each pass. Writing it as d * d avoids computing a square root on floating-point numbers. This lesson keeps the simpler range loop because it matches the statement's budget, but the idea is the natural next step.

Edge cases and common mistakes

0 and 1. Both return false. Without the first check, 1 would crash the loop and 0 would too.
Large inputs. A prime near a billion makes the loop run about a billion times, which is slow. That is the cost of the O(n) approach.
2. The smallest prime. The loop range is empty and the method returns true.
Starting the loop at 1. Every number is divisible by 1, so every input would be reported as not prime.
Ending the range at n inclusive. Using 2...n includes n itself, which always divides n, so every number would come out not prime.
Returning true inside the loop. One non-divisor proves nothing, so true belongs after the loop.

Testing

0, 1, 4, 6 and 100 give false.
2, 3, 31 and 97 give true.

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

Start learning free