Check if Number is Prime in DSA Python - Execution Trace

Concept Flow - Check if Number is Prime

Start with number n

↓

Check if n <= 1?

Yes→Not prime, stop

No↓

Set divisor i = 2

↓

Check if i * i <= n?

No→Prime, stop

Yes↓

Check if n % i == 0?

Yes→Not prime, stop

No↓

Increment i by 1

↩Back to check i * i <= n

Start from 2 and check divisors up to square root of n; if any divides n, it's not prime.

Execution Sample

DSA Python

def is_prime(n):
    if n <= 1:
        return False
    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += 1
    return True

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

Execution Table

Step	Operation	i	Condition i*i <= n	Check n % i == 0	Result	Notes
1	Check if n <= 1	-	n=17 > 1	-	-	Continue to divisor check
2	Set i = 2	2	2*2=4 <= 17 True	-	-	Start divisor loop
3	Check if 17 % 2 == 0	2	4 <= 17 True	17 % 2 = 1 != 0	No divisor	Increment i
4	Increment i	3	3*3=9 <= 17 True	-	-	Next divisor
5	Check if 17 % 3 == 0	3	9 <= 17 True	17 % 3 = 2 != 0	No divisor	Increment i
6	Increment i	4	4*4=16 <= 17 True	-	-	Next divisor
7	Check if 17 % 4 == 0	4	16 <= 17 True	17 % 4 = 1 != 0	No divisor	Increment i
8	Increment i	5	5*5=25 <= 17 False	-	-	Exit loop, prime confirmed
9	Return True	-	-	-	True	Number 17 is prime

💡 Loop ends when i*i > n; no divisor found, so number is prime.

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	After Step 8	Final
n	17	17	17	17	17	17
i	-	2	3	4	5	5
Result	-	-	-	-	-	True

Key Moments - 3 Insights

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

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

Why return False immediately when n % i == 0?

Because finding any divisor means n is not prime, so no need to check further (see execution_table row 3).

What happens if n is less than or equal to 1?

The function returns False immediately since numbers <= 1 are not prime (see execution_table row 1).

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of i when the loop condition i*i <= n becomes false?

A 4

B 5

C 6

D 3

💡 Hint

Check the 'Condition i*i <= n' column in rows 7 and 8.

At which step does the function confirm that 17 is prime?

A Step 8

B Step 3

C Step 9

D Step 1

💡 Hint

Look at the 'Result' and 'Notes' columns for when True is returned.

If n was 15 instead of 17, at which step would the function return False?

A Step 5

B Step 3

C Step 7

D Step 9

💡 Hint

Check when n % i == 0 is True for n=15; 15 % 3 == 0.

Concept Snapshot

Check if number n is prime:
- If n <= 1, return False
- For i from 2 to sqrt(n):
  - If n % i == 0, return False
- If no divisor found, return True
Use i*i <= n for efficiency.

Full Transcript

This visualization shows how to check if a number is prime by testing divisors from 2 up to the square root of the number. We start by checking if the number is less than or equal to 1, which is not prime. Then we set a divisor i to 2 and check if i squared is less than or equal to the number. If yes, we check if the number is divisible by i. If divisible, the number is not prime and we stop. If not, we increment i and repeat. If no divisors are found by the time i squared exceeds the number, the number is prime. The execution table traces these steps with the example number 17, showing the divisor checks and the final result.