Check if Number is Prime in DSA Javascript - Execution Trace

Concept Flow - Check if Number is Prime

Start with number n

↓

Check if n <= 1?

Yes→Not Prime

No↓

Set divisor = 2

↓

Is divisor * divisor <= n?

No→Prime

Yes↓

Check if n % divisor == 0?

Yes→Not Prime

No↓

Increment divisor by 1

↩Back to divisor check

Start by checking if the number is less than or equal to 1 (not prime). Then test divisors from 2 up to the square root of the number. If any divisor divides the number evenly, it is not prime. Otherwise, it is prime.

Execution Sample

DSA Javascript

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

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

Execution Table

Step	Operation	Divisor (i)	Condition (i*i <= n)	Divides n? (n % i == 0)	Result	Reasoning
1	Check if n <= 1	-	-	-	False	n=7 is greater than 1, continue
2	Set divisor i = 2	2	2*2=4 <= 7 (True)	7 % 2 = 1 (No)	Continue	2 does not divide 7
3	Increment divisor i = 3	3	3*3=9 <= 7 (False)	-	Prime	No divisor found, 7 is prime
4	Exit	-	-	-	-	Loop ends as i*i > n

💡 Loop stops when divisor squared is greater than n, confirming primality if no divisor found.

Variable Tracker

Variable	Start	After Step 2	After Step 3	Final
n	7	7	7	7
i (divisor)	-	2	3	3
Result	-	Continue	Prime	Prime

Key Moments - 3 Insights

Why do we check divisors only up to the square root of n?

Because if n has a divisor larger than its square root, it must have a smaller corresponding divisor. Checking up to sqrt(n) is enough to find any divisor. See execution_table rows 2 and 3 where i*i <= n controls the loop.

Why is n <= 1 not considered prime?

By definition, prime numbers are greater than 1. The first step in execution_table row 1 checks this and returns false immediately.

What happens if n is divisible by i?

If n % i == 0 is true, the function returns false immediately, meaning n is not prime. This is shown in execution_table row 2 where the check fails and continues, but if it were true, it would return false.

Visual Quiz - 3 Questions

Look at the execution_table, what is the divisor i when the loop stops?

A 2

B 3

C 4

D 1

💡 Hint

Check the divisor values in execution_table rows 2 and 3 where the loop condition fails at i=3.

At which step does the function decide the number is prime?

A Step 1

B Step 2

C Step 3

D Step 4

💡 Hint

Look at execution_table row 3 where the condition i*i <= n becomes false and the result is 'Prime'.

If n was 9, what would happen at divisor i=3 according to the execution logic?

A The function returns true (prime)

B The function returns false (not prime)

C The loop continues to i=4

D The function skips divisor 3

💡 Hint

Recall that 9 % 3 == 0 means n is divisible by i, so the function returns false immediately.

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
Only check divisors up to sqrt(n) for efficiency.

Full Transcript

This concept checks if a number is prime by testing divisors from 2 up to the square root of the number. It starts by excluding numbers less than or equal to 1. Then it loops through possible divisors, checking if any divide the number evenly. If a divisor is found, the number is not prime. If no divisors are found by the time the divisor squared exceeds the number, the number is prime.

Practice

1. What does it mean if a number is prime?

easy

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

B. It is divisible by all numbers less than itself.

C. It is an even number greater than 2.

D. It is a number that ends with digit 5.

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

   It has exactly two distinct positive divisors: 1 and itself. matches the definition exactly. Other options describe incorrect properties.

3. Final Answer:

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

4. Quick Check:

   Prime number = two divisors only [OK]

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

Common Mistakes:

• Thinking all even numbers are prime
• Confusing prime with numbers ending in 5
• Assuming prime numbers have many divisors

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

easy

A. for(let i = 2; i < n; i++) { if(n % i === 0) return false; } return true;

B. for(let i = 2; i <= n; i++) { if(n % i === 0) return false; } return true;

C. for(let i = 1; i < n; i++) { if(n % i === 0) return false; } return true;

D. for(let i = 2; i < n; i++) { if(n % i !== 0) return false; } return true;

Solution

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

   We check divisors from 2 up to but not including n to find if n is divisible by any number other than 1 and itself.

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

   for(let i = 2; i < n; i++) { if(n % i === 0) return false; } return true; correctly loops from 2 to n-1 and returns false if divisible. for(let i = 2; i <= n; i++) { if(n % i === 0) return false; } return true; incorrectly includes n itself, always returning false. for(let i = 1; i < n; i++) { if(n % i === 0) return false; } return true; starts from 1, which divides all numbers. for(let i = 2; i < n; i++) { if(n % i !== 0) return false; } return true; returns false if not divisible, which is wrong logic.

3. Final Answer:

   for(let i = 2; i < n; i++) { if(n % i === 0) return false; } return true; -> Option A

4. Quick Check:

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

Hint: Check divisors from 2 up to n-1 only [OK]

Common Mistakes:

• Including n in divisor check
• Starting loop from 1
• Using wrong condition for divisibility

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

function isPrime(n) {
  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(29));

medium

A. false

B. true

C. undefined

D. Error

Solution

1. Step 1: Understand the prime check logic with square root optimization

   The function returns false if n is less than or equal to 1. Then it checks divisors from 2 up to square root of n. If any divisor divides n, it returns false; otherwise true.

2. Step 2: Trace the function call with n = 29

   29 > 1, loop runs i from 2 to 5 (since sqrt(29) ≈ 5.38). None of 2,3,4,5 divides 29 evenly, so loop completes and returns true.

3. Final Answer:

   true -> Option B

4. Quick Check:

   29 is prime, function returns true [OK]

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

Common Mistakes:

• Looping up to n instead of sqrt(n)
• Not handling n <= 1 case
• Returning wrong boolean values

4. Find the error in this code that checks if a number num is prime:

function checkPrime(num) {
  if (num < 2) return false;
  for (let i = 2; i < num / 2; i++) {
    if (num % i === 0) return false;
  }
  return true;
}

medium

A. The function should return false if num is 2.

B. Loop should run until i <= Math.sqrt(num) for efficiency.

C. The condition num < 2 should be num <= 2.

D. Loop should run until i <= num / 2, not i < num / 2.

Solution

1. Step 1: Identify the logic error by tracing with num=4

   For num=4 (not prime), if(4 < 2) false; for(let i=2; i < 4/2; i++) i.e. i < 2 false, loop skips, returns true incorrectly.

2. Step 2: Determine the cause and fix

   The i < num/2 fails when num/2 is integer equal to starting i (e.g., num=4), skipping the check. Use i <= num/2 to include boundary. Loop should run until i <= num / 2, not i < num / 2. identifies this error; B offers further efficiency.

3. Final Answer:

   Loop should run until i <= num / 2, not i < num / 2. -> Option D

4. Quick Check:

   For num=4, i <= num/2 checks i=2 [OK]

Hint: Use i <= num/2 to include boundary divisors [OK]

Common Mistakes:

• Using i < num/2 which skips checks for composites like 4
• Incorrect boundary conditions in loop
• Wrong base case for numbers less than 2

5. You want to write a function that returns all prime numbers up to a given number max. Which approach is best to optimize performance?

hard

A. Return all numbers from 2 to max without any checks.

B. Check each number from 2 to max by testing divisibility up to half of that number.

C. Check each number from 2 to max using a loop up to sqrt of that number to test primality.

D. Check each number from 2 to max by testing divisibility up to the number itself minus one.

Solution

1. Step 1: Understand the problem of finding primes up to max

   We need to test each number from 2 to max to see if it is prime efficiently.

2. Step 2: Evaluate each approach for efficiency

   Check each number from 2 to max using a loop up to sqrt of that number to test primality. uses the efficient method of checking divisibility only up to sqrt of each number, reducing unnecessary checks. Options B and C check more divisors than needed, causing slower performance. Return all numbers from 2 to max without any checks. ignores primality checks.

3. Final Answer:

   Check each number from 2 to max using a loop up to sqrt of that number to test primality. -> Option C

4. Quick Check:

   Use sqrt limit for divisor checks to optimize prime search [OK]

Hint: Test divisors only up to sqrt of each number [OK]

Common Mistakes:

• Checking divisors up to number itself
• Ignoring efficiency in prime checking
• Returning all numbers without checks