Check if Number is Prime in DSA Javascript

Mental Model

A prime number is only divisible by 1 and itself. To check if a number is prime, we test if any smaller number divides it evenly.

Analogy: Imagine you have a group of identical candies and want to split them evenly into smaller groups. If you can only split them into one big group or all single candies, the number of candies is prime.

Number: 7
Check divisors: 2 -> 3 -> 4 -> 5 -> 6
No divisor divides 7 evenly -> 7 is prime

Dry Run Walkthrough

Input: Check if number 7 is prime

Goal: Determine if 7 has any divisor other than 1 and itself

Step 1: Check if 7 is less than 2 (not prime if yes)

7 (number to check)

Why: Numbers less than 2 are not prime

Step 2: Test divisor 2: 7 % 2 != 0, so continue

Divisor = 2, 7 % 2 = 1 (not zero)

Why: 2 does not divide 7 evenly, so 7 might still be prime

Step 3: Stop checking at divisor > sqrt(7) ≈ 2.64, no divisors found

No divisor found that divides 7 evenly

Why: No divisor found means 7 is prime

Result:

7 is prime

Annotated Code

DSA Javascript

class PrimeChecker {
  static isPrime(num) {
    if (num < 2) return false; // Numbers less than 2 are not prime
    const limit = Math.floor(Math.sqrt(num));
    for (let divisor = 2; divisor <= limit; divisor++) {
      if (num % divisor === 0) {
        return false; // Found a divisor, number is not prime
      }
    }
    return true; // No divisors found, number is prime
  }
}

// Driver code
const numberToCheck = 7;
const result = PrimeChecker.isPrime(numberToCheck);
console.log(`${numberToCheck} is ${result ? 'prime' : 'not prime'}`);

if (num < 2) return false; // Numbers less than 2 are not prime

Handle numbers less than 2 as not prime

const limit = Math.floor(Math.sqrt(num));

Set upper limit to square root of number to reduce checks

for (let divisor = 2; divisor <= limit; divisor++) {

Check all divisors from 2 up to limit

if (num % divisor === 0) { return false; }

If divisor divides number evenly, number is not prime

return true; // No divisors found, number is prime

If 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 the number

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

vs Alternative: Checking all numbers up to n would be O(n), which is slower; limiting to √n improves efficiency

Edge Cases

Number less than 2 (e.g., 0 or 1)

Returns false immediately as these are not prime

DSA Javascript

if (num < 2) return false; // Numbers less than 2 are not prime

Number is 2 (smallest prime)

Returns true since 2 is prime

DSA Javascript

for (let divisor = 2; divisor <= limit; divisor++) {

Large prime number

Efficiently checks divisors only up to square root, returns true if no divisor found

DSA Javascript

const limit = Math.floor(Math.sqrt(num));

When to Use This Pattern

When you need to check if a number has no divisors other than 1 and itself, use the prime check pattern by testing divisors up to the square root.

Common Mistakes

Mistake: Checking divisors up to the number itself instead of square root
Fix: Limit divisor checks to the square root of the number to improve efficiency

Mistake: Not handling numbers less than 2 correctly
Fix: Add a condition to return false for numbers less than 2

Summary

Checks if a number is prime by testing divisors up to its square root.

Use when you need to quickly determine if a number has no divisors other than 1 and itself.

Only check divisors up to the square root to save time and avoid unnecessary work.

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