Why Check if Number is Prime in DSA Javascript?

The Big Idea

What if you could tell if a number is prime without checking every single smaller number?

The Scenario

Imagine you want to find out if a number is prime by checking every single number smaller than it one by one, like counting all the way from 1 to that number and seeing if it divides evenly.

The Problem

This manual way is very slow and tiring, especially for big numbers. It takes a lot of time and you can easily make mistakes by missing some numbers or checking too many unnecessary ones.

The Solution

Using a smart method to check if a number is prime, we only test divisors up to the square root of the number. This saves time and effort, making the check fast and reliable.

Before vs After

✗ Before

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

✓ After

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

What It Enables

This lets us quickly and easily find out if numbers are prime, even when they are very large.

Real Life Example

Prime numbers are used in secret codes that keep your online messages safe, so checking primes fast helps protect your privacy.

Key Takeaways

Manual checking every number is slow and error-prone.

Checking up to the square root is faster and simpler.

Fast prime checks help in security and math problems.

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