Check if Number is Prime in DSA Rust

Mental Model

A prime number is a number greater than 1 that has no divisors other than 1 and itself.

Analogy: Think of a prime number like a special lock that only opens with two keys: 1 and itself. If any other key fits, it's not prime.

Number: 7
Check divisors: 2, 3, 4, 5, 6
No divisor fits -> prime

7
↑
Check divisors -> 2, 3, 4, 5, 6
No divisor divides 7 exactly

Dry Run Walkthrough

Input: Check if number 7 is prime

Goal: Determine if 7 has any divisors other than 1 and 7

Step 1: Check if 7 is less than or equal to 1

7 (number to check)

Why: Numbers less than or equal to 1 are not prime

Step 2: Check divisibility by 2

7 % 2 != 0

Why: 2 does not divide 7 exactly, so continue checking

Step 3: Check divisibility by 3

7 % 3 != 0

Why: 3 does not divide 7 exactly, so continue checking

Step 4: Check divisibility by 4

4 > sqrt(7) ≈ 2.64, stop checking

Why: No need to check divisors greater than square root

Result:

7 is prime because no divisor other than 1 and 7 divides it exactly

Annotated Code

DSA Rust

fn is_prime(n: u32) -> bool {
    if n <= 1 {
        return false; // numbers <= 1 are not prime
    }
    let limit = (n as f64).sqrt() as u32;
    for i in 2..=limit {
        if n % i == 0 {
            return false; // found a divisor, not prime
        }
    }
    true // no divisors found, number is prime
}

fn main() {
    let number = 7;
    if is_prime(number) {
        println!("{} is prime", number);
    } else {
        println!("{} is not prime", number);
    }
}

if n <= 1 {

check if number is less than or equal to 1 -- not prime

let limit = (n as f64).sqrt() as u32;

calculate square root limit to reduce divisor checks

for i in 2..=limit {

iterate from 2 up to square root to check divisors

if n % i == 0 {

if divisor found, number is not prime

true

no divisors found, number is prime

Output

7 is prime

Complexity Analysis

Time: O(√n) because we only check divisors up to the square root of n

Space: O(1) because we use a fixed amount of extra space regardless of input size

vs Alternative: Naive approach checks all numbers up to n-1, which is O(n), so this method is faster by reducing checks to √n

Edge Cases

number is 0 or 1

returns false because 0 and 1 are not prime

DSA Rust

if n <= 1 { return false; }

number is 2 (smallest prime)

returns true because 2 is prime

DSA Rust

for i in 2..=limit { ... } skips as limit is 1

number is a perfect square (e.g., 9)

returns false because divisor found at sqrt

DSA Rust

if n % i == 0 { return false; }

When to Use This Pattern

When you need to check if a number is prime, use the square root divisor check pattern because it efficiently reduces the number of checks needed.

Common Mistakes

Mistake: Checking divisors up to n-1 instead of square root of n
Fix: Only check divisors up to the square root of n to improve efficiency

Summary

Checks if a number has any divisors other than 1 and itself to determine primality.

Use when you need to quickly verify if a number is prime without checking all smaller numbers.

Only check divisors up to the square root of the number because larger divisors repeat smaller ones.

Practice

1. What does it mean for a number to be prime?

easy

A. It has more than two divisors.

B. It is divisible by 2 only.

C. It is an even number greater than 2.

D. It has exactly two distinct positive divisors: 1 and itself.

Solution

1. Step 1: Understand the definition of prime number

   A prime number is a number greater than 1 that has no divisors other than 1 and itself.

2. Step 2: Compare options with definition

   Only It has exactly two distinct positive divisors: 1 and itself. correctly states this definition.

3. Final Answer:

   It has exactly two distinct positive divisors: 1 and itself. -> Option D

4. Quick Check:

   Prime = two divisors [OK]

Hint: Prime numbers have only 1 and itself as divisors [OK]

Common Mistakes:

• Thinking even numbers are always prime
• Confusing prime with odd numbers
• Assuming 1 is prime

2. Which of the following Rust code snippets correctly checks if a number n is prime?

easy

A. for i in 1..n { if n % i == 0 { return false; } } true

B. for i in 2..n { if n % i == 0 { return false; } } true

C. for i in 2..=n { if n % i == 0 { return false; } } true

D. for i in 2..n { if n % i != 0 { return false; } } true

Solution

1. Step 1: Analyze the loop range for divisor checking

   We check divisors from 2 up to n-1 (exclusive of n) to find if any divides n.

2. Step 2: Check each option's loop and condition

   for i in 2..n { if n % i == 0 { return false; } } true correctly loops from 2 to n-1 and returns false if divisor found; others have errors like including n or wrong condition.

3. Final Answer:

   for i in 2..n { if n % i == 0 { return false; } } true -> Option B

4. Quick Check:

   Loop 2 to n-1 and check divisibility [OK]

Hint: Loop from 2 to n-1 to check divisors [OK]

Common Mistakes:

• Including n in the loop range
• Starting loop from 1 instead of 2
• Using wrong condition for divisibility

3. What is the output of this Rust function call: is_prime(11)?

fn is_prime(n: u32) -> bool {
    if n <= 1 { return false; }
    for i in 2..n {
        if n % i == 0 {
            return false;
        }
    }
    true
}

medium

A. true

B. false

C. panic at runtime

D. compile error

Solution

1. Step 1: Check input and loop behavior for n=11

   11 is greater than 1, so the function proceeds to loop from 2 to 10 checking divisibility.

2. Step 2: Test divisibility of 11 by numbers 2 to 10

   11 is not divisible by any number between 2 and 10, so loop completes without returning false.

3. Final Answer:

   true -> Option A

4. Quick Check:

   11 is prime, so function returns true [OK]

Hint: Prime numbers return true after no divisors found [OK]

Common Mistakes:

• Assuming 11 is not prime
• Confusing loop range
• Expecting runtime errors incorrectly

4. Identify the bug in this Rust function that checks if a number is prime:

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

medium

A. Missing return type in function signature

B. Condition should be n <= 1 instead of n < 2

C. Loop includes n, causing always false for n > 1

D. Loop should start from 1 instead of 2

Solution

1. Step 1: Analyze the loop range 2..=n

   The loop includes n itself, so n % n == 0 is always true, causing immediate false return.

2. Step 2: Understand correct loop range

   Loop should be 2..n (exclusive of n) to avoid checking n against itself.

3. Final Answer:

   Loop includes n, causing always false for n > 1 -> Option C

4. Quick Check:

   Loop must exclude n to avoid false negatives [OK]

Hint: Exclude n from divisor loop to avoid false negatives [OK]

Common Mistakes:

• Including n in divisor checks
• Wrong loop start index
• Misunderstanding return conditions

5. You want to optimize prime checking for large numbers by only checking divisors up to the square root of n. Which Rust code snippet correctly implements this?

hard

A. for i in 2..=((n as f64).sqrt() as u32) { if n % i == 0 { return false; } } true

B. for i in 2..n { if n % i == 0 { return false; } } true

C. for i in 2..=(n / 2) { if n % i == 0 { return false; } } true

D. for i in 1..=((n as f64).sqrt() as u32) { if n % i == 0 { return false; } } true

Solution

1. Step 1: Understand optimization using square root

   Checking divisors up to sqrt(n) is enough because larger factors pair with smaller ones.

2. Step 2: Analyze each option's loop range and correctness

   for i in 2..=((n as f64).sqrt() as u32) { if n % i == 0 { return false; } } true correctly casts n to float, computes sqrt, casts back to u32, and loops up to that value.

3. Final Answer:

   for i in 2..=((n as f64).sqrt() as u32) { if n % i == 0 { return false; } } true -> Option A

4. Quick Check:

   Loop up to sqrt(n) for efficient prime check [OK]

Hint: Check divisors only up to sqrt(n) for efficiency [OK]

Common Mistakes:

• Checking divisors beyond sqrt(n)
• Starting loop from 1 instead of 2
• Incorrect casting causing errors