Check if Number is Prime in DSA Rust - Execution Trace

Concept Flow - Check if Number is Prime

Start with number n

↓

Check if n <= 1?

Yes→Not Prime, Stop

No↓

Set divisor = 2

↓

Is divisor * divisor <= n?

No→Prime, Stop

Yes↓

Check if n % divisor == 0?

Yes→Not Prime, Stop

No↓

Increment divisor by 1

↩Back to divisor * divisor <= n check

Start checking divisors from 2 up to sqrt(n). If any divides n exactly, n is not prime. Otherwise, n is prime.

Execution Sample

DSA Rust

fn is_prime(n: u32) -> bool {
    if n <= 1 {
        return false;
    }
    let mut divisor = 2;
    while divisor * divisor <= n {
        if n % divisor == 0 {
            return false;
        }
        divisor += 1;
    }
    true
}

This function checks if a number n is prime by testing divisors from 2 up to sqrt(n).

Execution Table

Step	Operation	divisor	Condition divisor*divisor <= n	Check n % divisor == 0	Result	Visual State
1	Start with n=11	-	-	-	-	n=11, divisor not set
2	Check if n <= 1	-	-	-	False	Proceed to divisor check
3	Set divisor = 2	2	2*2=4 <= 11 True	11 % 2 == 1 False	Continue	divisor=2
4	Increment divisor	3	3*3=9 <= 11 True	11 % 3 == 2 False	Continue	divisor=3
5	Increment divisor	4	4*4=16 <= 11 False	-	No divisor found, prime	divisor=4
6	Return result	-	-	-	True	11 is prime

💡 Loop ends when divisor*divisor > n (step 5), no divisor found, so number is prime.

Variable Tracker

Variable	Start	After Step 3	After Step 4	After Step 5	Final
n	11	11	11	11	11
divisor	-	2	3	4	4
Result	-	-	-	-	True

Key Moments - 3 Insights

Why do we check divisor * divisor <= n instead of divisor <= n?

Because if n has a divisor larger than sqrt(n), it must have a smaller one below sqrt(n). Checking up to sqrt(n) is enough and efficient (see execution_table step 3 and 5).

What happens if n is 1 or less?

The function immediately returns false because numbers less than or equal to 1 are not prime (see execution_table step 2).

Why do we return false immediately when n % divisor == 0?

Because finding any divisor means n is divisible by a number other than 1 and itself, so it is not prime (see execution_table step 3 and 4).

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the value of divisor and the result of n % divisor == 0?

A divisor=3, n % divisor == 0 is True

B divisor=3, n % divisor == 0 is False

C divisor=4, n % divisor == 0 is False

D divisor=2, n % divisor == 0 is True

💡 Hint

Check the 'divisor' and 'Check n % divisor == 0' columns in execution_table row 4.

At which step does the loop condition divisor * divisor <= n become false?

A Step 3

B Step 4

C Step 5

D Step 6

💡 Hint

Look at the 'Condition divisor*divisor <= n' column in execution_table.

If n was 9 instead of 11, at which step would the function return false?

A Step 3

B Step 4

C Step 5

D Step 6

💡 Hint

Think about when 9 % divisor == 0 would be true for divisor starting at 2.

Concept Snapshot

fn is_prime(n: u32) -> bool {
  if n <= 1 { return false; }
  let mut divisor = 2;
  while divisor * divisor <= n {
    if n % divisor == 0 { return false; }
    divisor += 1;
  }
  true
}

Checks divisors from 2 to sqrt(n). Returns false if divisible, else true.

Full Transcript

This Rust function checks if a number n is prime by testing divisors from 2 up to the square root of n. It starts by returning false if n is less than or equal to 1. Then it sets divisor to 2 and loops while divisor squared is less than or equal to n. Inside the loop, if n is divisible by divisor, it returns false immediately. Otherwise, it increments divisor and continues. If no divisor divides n, it returns true, meaning n is prime. The execution table shows this process step by step for n=11, where divisors 2 and 3 are tested and no divisor divides 11, so the function returns true.

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