Check if Number is Prime in DSA Javascript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a prime number?

A prime number is a number greater than 1 that has no divisors other than 1 and itself.

intermediate

Why do we only check divisors up to the square root of a number when testing for primality?

Because if a number has a divisor larger than its square root, it must also have a smaller divisor below the square root. So checking up to the square root is enough.

beginner

What is the first step to check if a number n is prime?

Check if n is less than 2. If yes, it is not prime because primes start from 2.

beginner

How do you check if a number n is divisible by another number i?

If n % i equals 0, then n is divisible by i.

beginner

What does it mean if a number n is not divisible by any number from 2 to sqrt(n)?

It means n is a prime number.

What is the smallest prime number?

A 1

B 0

C 3

D 2

2 is the smallest prime number because it is greater than 1 and only divisible by 1 and itself.

Which of these numbers is NOT prime?

A 5

B 7

C 9

D 11

9 is not prime because it is divisible by 3.

When checking if 29 is prime, up to which number should you check divisors?

A 5

B 14

C 6

D 29

Check divisors up to the square root of 29, which is about 5.38, so check up to 5.

If a number n is divisible by 2, what can you say about n?

A n is even and not prime (except 2)

B n is 1

C n is odd

D n is prime

If n is divisible by 2 and n is not 2, then n is even and not prime.

Which condition means a number is NOT prime?

A Divisible only by 1 and itself

B Divisible by a number other than 1 and itself

C Greater than 1

D Equal to 2

If a number is divisible by any number other than 1 and itself, it is not prime.

Explain how to check if a number is prime using a simple step-by-step method.

Think about dividing the number by smaller numbers to find factors.

Why is it enough to check divisors only up to the square root of a number when testing for primality?

Imagine factor pairs like two numbers multiplying to the target number.

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