Check if Number is Prime in DSA Typescript - 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

↓

Check if 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 Typescript

function isPrime(n: number): boolean {
  if (n <= 1) return false;
  for (let i = 2; i * i <= n; i++) {
    if (n % i === 0) return false;
  }
  return true;
}

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	Reasoning
1	Start	-	-	-	-	Check if n <= 1; n=11 > 1, continue
2	Set i=2	2	2*2=4 <= 11: True	11 % 2 == 0? False	Continue	2 does not divide 11
3	Increment i=3	3	3*3=9 <= 11: True	11 % 3 == 0? False	Continue	3 does not divide 11
4	Increment i=4	4	4*4=16 <= 11: False	-	Prime	No divisor found up to sqrt(11)
5	End	-	-	-	Return true	Number 11 is prime

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

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	Final
n	11	11	11	11	11
i	-	2	3	4	4
Result	-	Continue	Continue	Prime	Prime

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 saves time. See execution_table rows 2-4.

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

Because finding any divisor means n is not prime. No need to check further. This is shown in execution_table row 3 where the check fails and continues.

What happens if n is 1 or less?

The function returns false immediately since 1 and below are not prime numbers. This is step 1 in execution_table.

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 2

B 4

C 3

D 5

💡 Hint

Check the 'Condition i*i <= n' column in execution_table row 4.

At which step does the function decide that 11 is prime?

A Step 4

B Step 2

C Step 3

D Step 5

💡 Hint

Look at the 'Result' and 'Reasoning' columns in execution_table row 4.

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

A Step 2

B Step 4

C Step 3

D Step 5

💡 Hint

9 % 3 == 0, so check execution_table logic for divisor found.

Concept Snapshot

Check if n <= 1: return false
Loop i from 2 to sqrt(n): if n % i == 0 return false
If no divisor found, return true
Only check up to i*i <= n for efficiency
Immediate return on first divisor found

Full Transcript

To check if a number n is prime, first verify if n is greater than 1. If not, it is not prime. Then, start checking divisors from 2 up to the square root of n. For each divisor i, if n is divisible by i, return false immediately. If no divisors are found by the time i*i exceeds n, return true. This method efficiently determines primality by reducing unnecessary checks.

Practice

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

easy

A. It is divisible by 2 only.

B. It has more than two divisors.

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 the 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 number = two divisors [OK]

Hint: Prime means only divisible by 1 and itself [OK]

Common Mistakes:

• Thinking even numbers are always prime
• Confusing prime with odd numbers
• Believing prime numbers have multiple divisors

2. Which of the following TypeScript function signatures correctly checks if a number is prime?

easy

A. function isPrime(n: boolean): string

B. function isPrime(n: string): number

C. function isPrime(n: number): boolean

D. function isPrime(): void

Solution

1. Step 1: Identify correct parameter and return types

   The function should take a number and return a boolean indicating prime or not.

2. Step 2: Match options with correct signature

   function isPrime(n: number): boolean matches: input number, output boolean.

3. Final Answer:

   function isPrime(n: number): boolean -> Option C

4. Quick Check:

   Input number, output boolean [OK]

Hint: Input number, output true/false for prime [OK]

Common Mistakes:

• Using wrong input types like string or boolean
• Returning wrong types like number or void
• Missing function parameters

3. What will be the output of the following TypeScript code?

function isPrime(n: number): boolean {
  if (n <= 1) return false;
  for (let i = 2; i <= Math.sqrt(n); i++) {
    if (n % i === 0) return false;
  }
  return true;
}
console.log(isPrime(11));

medium

A. true

B. false

C. undefined

D. SyntaxError

Solution

1. Step 1: Check input and initial condition

   Input is 11, which is greater than 1, so continue checking.

2. Step 2: Loop from 2 to sqrt(11) ≈ 3.3

   Check divisibility by 2 and 3. 11 % 2 != 0 and 11 % 3 != 0, so no divisor found.

3. Final Answer:

   true -> Option A

4. Quick Check:

   11 is prime = true [OK]

Hint: Check divisors up to square root only [OK]

Common Mistakes:

• Checking divisors beyond sqrt(n)
• Returning true too early
• Not handling n <= 1 correctly

4. Identify the error in this TypeScript function to check prime numbers:

function isPrime(n: number): boolean {
  if (n < 2) return false;
  for (let i = 2; i < n / 2; i++) {
    if (n % i === 0) return false;
  }
  return true;
}

medium

A. Loop should run until i <= Math.sqrt(n) for efficiency

B. Return type should be number, not boolean

C. Loop should run until i <= n / 2, not i < n / 2

D. Condition if (n < 2) should be if (n <= 1)

Solution

1. Step 1: Identify the logic error in loop condition

   The loop uses i < n / 2. For n=4, n/2=2, i=2 < 2 false; loop skips check for 2, returns true (but 4 not prime).

2. Step 2: Correct the loop bound

   For efficiency and correctness, the loop should run until i <= Math.sqrt(n) instead of n/2.

3. Final Answer:

   Loop should run until i <= Math.sqrt(n) for efficiency -> Option A

4. Quick Check:

   Loop bound to sqrt(n) is optimal and correct [OK]

Hint: Loop to i <= sqrt(n) for efficient prime check [OK]

Common Mistakes:

• Using i < n/2 instead of i <= n/2 in loop
• Wrong return type
• Incorrect boundary condition for n

5. You want to find all prime numbers between 10 and 20 using this function:

function isPrime(n: number): boolean {
  if (n <= 1) return false;
  for (let i = 2; i <= Math.sqrt(n); i++) {
    if (n % i === 0) return false;
  }
  return true;
}

Which of the following arrays correctly lists these primes?

medium

A. [10, 12, 14, 16, 18, 20]

B. [11, 13, 17, 19]

C. [11, 12, 13, 14, 15, 16, 17, 18, 19, 20]

D. [9, 11, 13, 15, 17, 19]

Solution

1. Step 1: Identify prime numbers between 10 and 20

   Check each number: 11 (prime), 12 (not), 13 (prime), 14 (not), 15 (not), 16 (not), 17 (prime), 18 (not), 19 (prime), 20 (not).

2. Step 2: List only primes in the array

   The primes are 11, 13, 17, and 19.

3. Final Answer:

   [11, 13, 17, 19] -> Option B

4. Quick Check:

   Primes 10-20 = [11,13,17,19] [OK]

Hint: Check each number with isPrime, collect true results [OK]

Common Mistakes:

• Including non-prime even numbers
• Including numbers less than 10 or greater than 20
• Confusing primes with odd numbers