Check if Number is Prime in DSA Javascript - Deep Dive

Overview - Check if Number is Prime

What is it?

A prime number is a whole number greater than 1 that can only be divided evenly by 1 and itself. Checking if a number is prime means finding out if it has no other divisors besides these two. This helps in many areas like cryptography, computer science, and math. Understanding how to check for primes is a basic but important skill.

Why it matters

Without knowing if numbers are prime, many security systems and algorithms would fail because prime numbers help create keys that keep data safe. Also, prime numbers are building blocks of all numbers, so understanding them helps in solving many math and programming problems efficiently. Without this concept, we would struggle with tasks like encryption and factorization.

Where it fits

Before this, learners should know basic programming concepts like loops and conditionals. After this, they can explore more complex number theory topics, algorithms for prime generation, and cryptographic applications.

Mental Model

Core Idea

A prime number has no divisors other than 1 and itself, so checking primality means testing divisibility by numbers up to its square root.

Think of it like...

Checking if a number is prime is like checking if a key fits only one lock perfectly without opening any other locks.

Number N
│
├─ Check divisibility by 2
├─ Check divisibility by 3
├─ ...
└─ Check divisibility by √N
If none divide N evenly -> Prime
Else -> Not Prime

Build-Up - 7 Steps

1

Foundation

Understanding Prime Numbers

Concept: What makes a number prime and why 1 is not prime.

A prime number is a number greater than 1 that has no divisors other than 1 and itself. For example, 2, 3, 5, and 7 are prime. The number 1 is not prime because it only has one divisor (itself).

Result

Clear definition of prime numbers and examples.

Understanding the definition of prime numbers is essential before checking if a number is prime.

2

Foundation

Basic Divisibility Check

Concept: How to check if one number divides another evenly.

To check if number A divides number B evenly, we use the modulo operation: B % A. If the result is 0, A divides B evenly. For example, 10 % 2 = 0 means 2 divides 10 evenly.

Result

Ability to test divisibility between two numbers.

Knowing how to test divisibility is the core operation for checking primality.

3

Intermediate

Naive Prime Check Algorithm

🤔Before reading on: Do you think checking divisibility up to N-1 or up to √N is enough? Commit to your answer.

Concept: Check divisibility from 2 up to N-1 to decide if N is prime.

To check if N is prime, test if any number from 2 to N-1 divides N evenly. If none do, N is prime. This is simple but slow for large N.

Result

Correctly identifies primes but inefficient for large numbers.

Understanding the naive approach helps appreciate why optimizations are needed.

4

Intermediate

Optimizing with Square Root Limit

🤔Before reading on: Do you think checking divisors beyond √N can find new factors? Commit to yes or no.

Concept: Only check divisibility up to the square root of N.

If N has a divisor larger than its square root, it must have a smaller paired divisor below the square root. So, checking up to √N is enough. This reduces the number of checks drastically.

Result

More efficient prime check with fewer divisibility tests.

Knowing the square root limit saves time and makes prime checking practical.

5

Intermediate

Skipping Even Numbers After 2

🤔Before reading on: Should we check even numbers after 2 when testing primality? Commit to yes or no.

Concept: After checking 2, skip even numbers to reduce checks.

Since even numbers greater than 2 are not prime, after testing divisibility by 2, we only check odd numbers up to √N. This halves the number of checks.

Result

Further optimized prime check with fewer iterations.

Skipping unnecessary checks improves efficiency without missing any factors.

6

Advanced

JavaScript Implementation of Prime Check

🤔Before reading on: Do you think the code should return true for 1? Commit to yes or no.

Concept: Write a complete JavaScript function to check primality using optimizations.

function isPrime(n) { if (n <= 1) return false; if (n === 2) return true; if (n % 2 === 0) return false; const limit = Math.floor(Math.sqrt(n)); for (let i = 3; i <= limit; i += 2) { if (n % i === 0) return false; } return true; } // Example usage: console.log(isPrime(11)); // true console.log(isPrime(15)); // false

Result

Outputs true for prime numbers and false for non-primes correctly.

Implementing the optimized algorithm in code solidifies understanding and shows practical use.

7

Expert

Advanced Optimizations and Limitations

🤔Before reading on: Can prime checking be done faster than O(√N) for any number? Commit to yes or no.

Concept: Discuss advanced methods like probabilistic tests and their tradeoffs.

For very large numbers, deterministic checks up to √N are slow. Probabilistic tests like Miller-Rabin can quickly check primality with high confidence but not absolute certainty. These are used in cryptography. Also, caching primes or using sieve methods helps when checking many numbers.

Result

Understanding of when and why advanced prime checks are used.

Knowing advanced methods prepares learners for real-world applications where speed and scale matter.

Under the Hood

The primality test works by checking if any number divides the target number evenly. Internally, the modulo operation calculates the remainder of division. If any divisor yields zero remainder, the number is composite. The square root optimization relies on the fact that factors come in pairs, one smaller and one larger than the square root, so checking beyond the square root is redundant.

Why designed this way?

Early mathematicians discovered prime numbers and their properties. The square root limit was found to reduce unnecessary checks, making primality testing feasible. Probabilistic tests were designed later to handle very large numbers efficiently, trading absolute certainty for speed.

┌───────────────┐
│ Input number N │
└──────┬────────┘
       │
       ▼
┌─────────────────────────────┐
│ Check if N <= 1 -> Not prime  │
├─────────────────────────────┤
│ Check if N == 2 -> Prime      │
├─────────────────────────────┤
│ Check if N % 2 == 0 -> Not prime │
├─────────────────────────────┤
│ For i = 3 to √N step 2       │
│   Check if N % i == 0        │
│   If yes -> Not prime         │
└─────────────────────────────┘
       │
       ▼
┌───────────────┐
│ Return Prime  │
└───────────────┘

Myth Busters - 4 Common Misconceptions

Quick: Is 1 considered a prime number? Commit to yes or no.

Common Belief: Many think 1 is prime because it is only divisible by itself.

Reality: 1 is not prime because prime numbers must have exactly two distinct divisors: 1 and itself. 1 has only one divisor.

Why it matters: Treating 1 as prime breaks many mathematical theorems and algorithms that rely on prime factorization.

Quick: Do you think checking divisibility beyond the square root of N can find new factors? Commit to yes or no.

Common Belief: Some believe you must check all numbers up to N-1 to be sure if N is prime.

Reality: Checking up to the square root of N is enough because factors come in pairs; one factor is always less than or equal to the square root.

Why it matters: Checking beyond the square root wastes time and slows down the algorithm unnecessarily.

Quick: Should we check even numbers after 2 when testing primality? Commit to yes or no.

Common Belief: People often check every number including even numbers after 2.

Reality: Even numbers greater than 2 are not prime, so checking them is redundant.

Why it matters: Skipping even numbers after 2 improves efficiency without missing any primes.

Quick: Can probabilistic prime tests guarantee 100% accuracy? Commit to yes or no.

Common Belief: Some think probabilistic tests always give correct answers.

Reality: Probabilistic tests give high confidence but not absolute certainty; they can have rare false positives.

Why it matters: Relying blindly on probabilistic tests without understanding their limits can cause security risks.

Expert Zone

1

Many prime checking algorithms use wheel factorization to skip multiples of small primes, further reducing checks.

2

Caching previously found primes can speed up checking multiple numbers by reducing repeated work.

3

Probabilistic tests like Miller-Rabin are often combined with deterministic checks for a balance of speed and certainty.

When NOT to use

For very large numbers (hundreds of digits), naive or square root checks are too slow. Use probabilistic tests like Miller-Rabin or AKS primality test instead. For checking many primes in a range, use sieve algorithms like the Sieve of Eratosthenes.

Production Patterns

In cryptography, prime checks use probabilistic tests for speed. In math software, caching and sieves are common. Web applications often use precomputed prime lists or fast libraries to avoid performance hits.

Connections

Sieve of Eratosthenes

Builds-on

Understanding individual prime checks helps grasp how sieves efficiently find many primes by marking multiples.

Cryptography

Application

Prime numbers are fundamental to encryption algorithms, so primality testing is critical for secure communication.

Factorization in Number Theory

Opposite process

Knowing primality helps in factorization, which breaks numbers into primes; both are key in understanding number structure.

Common Pitfalls

#1 Incorrectly treating 1 as a prime number.

Wrong approach:

function isPrime(n) {
if (n === 1) return true;
// rest of code
}

Correct approach:

function isPrime(n) {
if (n <= 1) return false;
// rest of code
}

Root cause:

Misunderstanding the definition of prime numbers and overlooking the special case of 1.

#2 Checking divisibility up to n-1 instead of √n, causing inefficiency.

Wrong approach:

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

Correct approach:

const limit = Math.floor(Math.sqrt(n));
for (let i = 2; i <= limit; i++) {
if (n % i === 0) return false;
}

Root cause:

Not knowing the mathematical property that factors come in pairs around the square root.

#3 Checking even numbers after 2 unnecessarily.

Wrong approach:

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

Correct approach:

if (n % 2 === 0) return false;
for (let i = 3; i <= limit; i += 2) {
if (n % i === 0) return false;
}

Root cause:

Not realizing that even numbers greater than 2 cannot be prime.

Key Takeaways

A prime number is only divisible by 1 and itself, and 1 is not prime.

Checking divisibility up to the square root of a number is enough to determine primality.

Skipping even numbers after 2 reduces the number of checks and improves efficiency.

Probabilistic tests offer fast primality checks for large numbers but trade absolute certainty.

Understanding primality is foundational for many algorithms, especially in cryptography and number theory.

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