Start learning free

LESSON 142 OF 414 · LOOPS & CONDITIONALS

Prime Number in Rust: Trial Division with a 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
    Ctrl + Enter to check

    RUST · LOOPS & CONDITIONALS

    Prime Number in Rust, explained

    Problem overview

    The function is_prime takes an integer n and returns true when it is prime and false otherwise. 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 statement asks for O(n) time and O(1) extra space. That allows a plain loop that tests every candidate divisor.

    Approach

    Turn the definition around. A number n is prime exactly when no number d with 1 < d < n divides it. So the function tries each d from 2 up to n - 1. The first divisor it finds proves that n is not prime, and the function can return false at once. If the loop ends without finding one, n is prime.

    A number d divides n when the remainder of n / d is zero, which Rust writes as n % d == 0.

    One input needs separate handling. Prime numbers start at 2, so 0, 1 and every negative number must give false. The loop alone would get these wrong, as the edge cases below show.

    Two examples traced

    For n = 6, the loop starts with d = 2. Since 6 % 2 is 0, the function returns false immediately, and the values 3, 4 and 5 are never tried.

    For n = 31, the remainders for d from 2 to 30 are all non-zero. For instance, 31 % 2 is 1, 31 % 3 is 1 and 31 % 5 is 1. The loop finishes without returning, and the final line returns true.

    Why this is the simple version

    The loop tests more candidates than it needs to. Any divisor of n above its square root pairs with a divisor below it, so a faster check could stop at the square root. This lesson keeps the straightforward loop, which matches the O(n) budget and makes the definition easy to see in the code.

    Step by step

    1. Reject numbers below 2. Check n < 2 first and return false. This covers 0, 1 and the negatives.
    2. Loop over the candidate divisors. The variable d runs from 2 up to n - 1. Inside the loop, test whether n % d == 0.
    3. Return false on the first divisor. One divisor between 2 and n - 1 is enough to rule out a prime, so there is no reason to keep looping.
    4. Return true after the loop. Reaching this line means no d divided n.

    The solution in Rust

    impl Solution {
    fn is_prime(n: i32) -> bool {
        if n < 2 {
            return false;
        }
        for d in 2..n {
            if n % d == 0 {
                return false;
            }
        }
        return true;
    }
}

    Some Rust details here:

    • 2..n excludes n. The range a..b includes a and stops before b, so d takes the values 2 to n - 1. Writing 2..=n would include n itself, and every number would then look divisible by itself.
    • An empty range is fine. When n is 2, the range 2..2 has no values, so the body never runs and the function returns true. A range whose start is past its end, such as 2..1, is also empty and does not panic.
    • The type of d is inferred. Because n % d mixes d with an i32, the compiler makes d an i32 too.
    • Early return. return false; leaves the function from inside the loop. The final return true; could also be written as the bare expression true, without return and the semicolon.
    • % keeps the sign of the dividend. In Rust, -4 % 2 is 0 and -5 % 3 is -2. This is why the n < 2 check has to come before the loop.

    Complexity

    Time: O(n). In the worst case, which is a prime, the loop runs n - 2 times and does one remainder operation each time. For a composite number the loop stops sooner, at its smallest divisor.

    Space: O(1). The function keeps only n and the loop variable d, no matter how large n is.

    Edge cases and common mistakes

    Most wrong answers on this problem come from the boundaries of the range or from the inputs below 2.

    • Forgetting the guard. Without the n < 2 check, is_prime(1) returns true, because the range 2..1 is empty and the loop is skipped. The same happens for 0 and for negative numbers.
    • Starting at 1. Every number is divisible by 1, so a loop that begins there rejects everything. Start at 2.
    • Going up to n inclusive. Every n divides itself, so 2..=n makes every number composite.
    • The number 2. It is the smallest prime and the only even one. The empty loop gives the correct true.
    • Using = for ==. if n % d = 0 does not compile. Comparison needs ==.

    Running time in practice

    Linear time is fine for small inputs, but it grows with the value of n, not with the number of digits. A prime near the top of the i32 range, about 2.1 billion, would need roughly two billion remainder operations. Composite numbers finish much sooner, because they stop at their smallest factor.

    Testing

    • n = 31 gives true.
    • n = 6 gives false.
    • n = 2 gives true, and n = 3 gives true.
    • n = 4 gives false.
    • n = 1 and n = 0 give false.
    • n = 97 gives true.
    Keep going with RustAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free