Check if Number is Prime in DSA Typescript - 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 whether it has any divisors other than these two. This helps us understand the building blocks of numbers, as primes are the basic units in multiplication. Knowing if a number is prime is important in many areas like security and math.

Why it matters

Without the ability to check for prime numbers, many systems like secure communication and encryption would fail, because they rely on prime numbers to keep information safe. Also, prime numbers help us understand patterns in math and solve problems involving factors and multiples. If we couldn't identify primes, many algorithms and technologies would be less efficient or impossible.

Where it fits

Before learning to check if a number is prime, you should understand basic division and loops in programming. After this, you can explore more advanced topics like prime factorization, cryptography, and efficient algorithms for large numbers.

Mental Model

Core Idea

A prime number has no divisors other than 1 and itself, so checking primality means testing if any number between 2 and the square root divides it evenly.

Think of it like...

Checking if a number is prime is like checking if a key fits any lock other than the main door and the front gate; if it fits none, it's a unique key (prime).

Number N
│
├─ Check divisors from 2 to √N
│   ├─ If any divides N evenly -> Not prime
│   └─ Else -> Prime
└─ Result: Prime or Not Prime

Build-Up - 7 Steps

1

Foundation

Understanding What Prime Means

Concept: Introduce the definition of prime numbers and what makes a number prime.

A prime number is a number greater than 1 that cannot be divided evenly by any other number except 1 and itself. For example, 2, 3, 5, and 7 are prime because no other numbers divide them without leaving a remainder. Numbers like 4 or 6 are not prime because they can be divided evenly by numbers other than 1 and themselves.

Result

You know which numbers are prime and which are not by their divisors.

Understanding the exact meaning of prime numbers is essential before trying to check them programmatically.

2

Foundation

Basic Division and Remainder Concept

Concept: Learn how to check if one number divides another evenly using remainder.

When you divide one number by another, if the remainder is zero, it means the second number divides the first evenly. For example, 10 divided by 2 leaves remainder 0, so 2 divides 10 evenly. In programming, the modulo operator (%) gives the remainder. If number % divisor === 0, divisor divides number evenly.

Result

You can test if one number divides another without remainder.

Knowing how to check divisibility is the core operation needed to test primality.

3

Intermediate

Simple Loop to Test Divisors

🤔Before reading on: Do you think checking all numbers from 2 up to the number itself is necessary to find if it's prime? Commit to your answer.

Concept: Use a loop to test every number from 2 up to one less than the number to see if it divides evenly.

To check if a number n is prime, start from 2 and go up to n-1. For each number i, check if n % i === 0. If yes, n is not prime. If no divisor is found, n is prime. This method works but can be slow for large numbers.

Result

You can determine primality by testing all possible divisors.

This brute force method is simple but inefficient; it sets the stage for optimization.

4

Intermediate

Optimizing by Checking up to Square Root

🤔Before reading on: Do you think checking divisors beyond the square root of a number can find new factors? Commit to yes or no.

Concept: You only need to check divisors up to the square root of the number because larger divisors would pair with smaller ones already checked.

If n = a * b, then one of a or b must be less than or equal to √n. So, checking divisors only up to √n is enough. For example, to check if 29 is prime, test divisors up to 5 (since 5²=25 < 29 and 6²=36 > 29). If no divisor divides evenly, 29 is prime.

Result

The primality check becomes faster by reducing the number of divisors tested.

Knowing the math behind divisor pairs lets us skip unnecessary checks, improving efficiency.

5

Intermediate

Handling Edge Cases and Small Numbers

Concept: Learn to handle numbers less than 2 and special cases like 2 and 3 correctly.

Numbers less than 2 are not prime by definition. The number 2 is the smallest prime and should be handled correctly. Also, 3 is prime. Make sure your code returns false for 0 and 1, and true for 2 and 3 without unnecessary checks.

Result

Your primality function correctly handles all inputs, including edge cases.

Handling edge cases prevents bugs and ensures your function works for all valid inputs.

6

Advanced

Efficient TypeScript Implementation

🤔Before reading on: Do you think using a for loop with early return improves performance over checking all divisors? Commit to yes or no.

Concept: Implement the prime check in TypeScript using a loop up to the square root and return early when a divisor is found.

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

Result

The function prints true for 29 and false for 30, correctly identifying primality.

Early return stops unnecessary checks, making the function efficient and easy to read.

7

Expert

Advanced Optimizations and Limitations

🤔Before reading on: Do you think checking only odd numbers after 2 can speed up the prime check? Commit to yes or no.

Concept: Skip even numbers after 2 and use other optimizations to reduce checks; understand limitations for very large numbers.

Since 2 is the only even prime, after checking 2, test only odd divisors. This halves the number of checks. For very large numbers, more advanced algorithms like Miller-Rabin or Sieve of Eratosthenes are used. Also, floating point precision can affect the square root calculation for huge numbers.

Result

The function becomes faster for large inputs but still limited for very large primes without advanced algorithms.

Knowing these optimizations and limits prepares you for real-world scenarios where performance matters.

Under the Hood

The primality check works by testing if any number divides the target number evenly. Internally, the modulo operation (%) calculates the remainder of division. If the remainder is zero, a divisor is found. The loop runs from 2 up to the square root of the number because factors come in pairs, and checking beyond the square root would be redundant. The early return stops the loop as soon as a divisor is found, saving time.

Why designed this way?

This method balances simplicity and efficiency. Checking all numbers up to n-1 is too slow, so limiting to the square root reduces work drastically. Early return avoids unnecessary checks once a divisor is found. Skipping even numbers after 2 further optimizes the process. These choices come from mathematical properties of numbers and practical performance needs.

Start
  │
  ▼
Check if n < 2 -> Yes -> Not prime
  │                 No ->
  ▼
Check if n == 2 or 3 -> Yes -> Prime
  │
  ▼
Calculate limit = floor(sqrt(n))
  │
  ▼
Loop i from 2 to limit
  │   ├─ If n % i == 0 -> Not prime (stop)
  │   └─ Else continue
  ▼
No divisors found -> Prime

Myth Busters - 4 Common Misconceptions

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

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 properties.

Quick: Do you think checking divisors beyond the square root 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 beyond the square root is unnecessary because any larger factor pairs with a smaller one already checked.

Why it matters: Not knowing this leads to inefficient code that wastes time checking redundant divisors.

Quick: Is 2 the only even prime number? Commit to yes or no.

Common Belief: People often think there are many even prime numbers.

Reality: 2 is the only even prime number; all other even numbers are divisible by 2 and thus not prime.

Why it matters: Failing to recognize this causes unnecessary checks and confusion in algorithms.

Quick: Can floating point errors affect prime checking for very large numbers? Commit to yes or no.

Common Belief: Many assume prime checking is always exact and unaffected by number size.

Reality: For very large numbers, floating point precision can cause incorrect square root calculations, leading to wrong results.

Why it matters: Ignoring this can cause subtle bugs in cryptography and scientific computations.

Expert Zone

1

Skipping even numbers after checking 2 reduces the number of iterations by about half, improving performance without changing correctness.

2

Using integer square root functions or bitwise operations can speed up the limit calculation in some languages.

3

For very large numbers, probabilistic tests like Miller-Rabin offer a tradeoff between speed and certainty, which is crucial in cryptography.

When NOT to use

This simple method is inefficient for very large numbers (hundreds of digits). Instead, use advanced algorithms like Miller-Rabin primality test or the Sieve of Eratosthenes for ranges. For cryptographic applications, probabilistic tests are preferred for speed and scalability.

Production Patterns

In production, primality checks are often part of key generation in encryption systems. Developers use optimized libraries implementing probabilistic tests. For small numbers, this simple method is used in educational tools, input validation, or small-scale applications.

Connections

Sieve of Eratosthenes

Builds-on

Understanding individual primality checks helps grasp how the sieve efficiently finds all primes up to a limit by marking multiples.

Cryptography

Application

Prime numbers are fundamental to encryption algorithms; knowing how to check primality is key to generating secure keys.

Factorization in Number Theory

Opposite process

Checking primality is the first step before factorization; understanding primes helps in breaking down numbers into their building blocks.

Common Pitfalls

#1 Checking divisibility up to n-1 instead of square root.

Wrong approach:

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

Correct approach:

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

Root cause:

Not knowing the mathematical property that factors come in pairs limits efficiency.

#2 Not handling numbers less than 2 correctly.

Wrong approach:

function isPrime(n: number): boolean {
for (let i = 2; i <= Math.sqrt(n); i++) {
if (n % i === 0) return false;
}
return true;
}

Correct approach:

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

Root cause:

Ignoring edge cases leads to incorrect results for inputs like 0 and 1.

#3 Checking even numbers after 2 unnecessarily.

Wrong approach:

function isPrime(n: number): boolean {
if (n < 2) return false;
for (let i = 2; i <= Math.floor(Math.sqrt(n)); i++) {
if (n % i === 0) return false;
}
return true;
}

Correct approach:

function isPrime(n: number): boolean {
if (n < 2) 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;
}

Root cause:

Not optimizing for known properties of primes causes unnecessary work.

Key Takeaways

A prime number is only divisible by 1 and itself, making it a fundamental building block in math.

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

Handling edge cases like numbers less than 2 and the number 2 itself is crucial for correctness.

Optimizations like skipping even numbers after 2 improve performance without changing results.

For very large numbers, advanced algorithms are needed beyond simple division checks.

Practice

1. What does it mean for a number to be prime?

easy

A. It is divisible by 2 only.

B. It has more than two divisors.

C. It is an even number greater than 2.

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

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 the definition

   Only It has exactly two distinct positive divisors: 1 and itself. correctly states this definition.

3. Final Answer:

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

4. Quick Check:

   Prime number = two divisors [OK]

Hint: Prime means only divisible by 1 and itself [OK]

Common Mistakes:

• Thinking even numbers are always prime
• Confusing prime with odd numbers
• Believing prime numbers have multiple divisors

2. Which of the following TypeScript function signatures correctly checks if a number is prime?

easy

A. function isPrime(n: boolean): string

B. function isPrime(n: string): number

C. function isPrime(n: number): boolean

D. function isPrime(): void

Solution

1. Step 1: Identify correct parameter and return types

   The function should take a number and return a boolean indicating prime or not.

2. Step 2: Match options with correct signature

   function isPrime(n: number): boolean matches: input number, output boolean.

3. Final Answer:

   function isPrime(n: number): boolean -> Option C

4. Quick Check:

   Input number, output boolean [OK]

Hint: Input number, output true/false for prime [OK]

Common Mistakes:

• Using wrong input types like string or boolean
• Returning wrong types like number or void
• Missing function parameters

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

function isPrime(n: number): boolean {
  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(11));

medium

A. true

B. false

C. undefined

D. SyntaxError

Solution

1. Step 1: Check input and initial condition

   Input is 11, which is greater than 1, so continue checking.

2. Step 2: Loop from 2 to sqrt(11) ≈ 3.3

   Check divisibility by 2 and 3. 11 % 2 != 0 and 11 % 3 != 0, so no divisor found.

3. Final Answer:

   true -> Option A

4. Quick Check:

   11 is prime = true [OK]

Hint: Check divisors up to square root only [OK]

Common Mistakes:

• Checking divisors beyond sqrt(n)
• Returning true too early
• Not handling n <= 1 correctly

4. Identify the error in this TypeScript function to check prime numbers:

function isPrime(n: number): boolean {
  if (n < 2) return false;
  for (let i = 2; i < n / 2; i++) {
    if (n % i === 0) return false;
  }
  return true;
}

medium

A. Loop should run until i <= Math.sqrt(n) for efficiency

B. Return type should be number, not boolean

C. Loop should run until i <= n / 2, not i < n / 2

D. Condition if (n < 2) should be if (n <= 1)

Solution

1. Step 1: Identify the logic error in loop condition

   The loop uses i < n / 2. For n=4, n/2=2, i=2 < 2 false; loop skips check for 2, returns true (but 4 not prime).

2. Step 2: Correct the loop bound

   For efficiency and correctness, the loop should run until i <= Math.sqrt(n) instead of n/2.

3. Final Answer:

   Loop should run until i <= Math.sqrt(n) for efficiency -> Option A

4. Quick Check:

   Loop bound to sqrt(n) is optimal and correct [OK]

Hint: Loop to i <= sqrt(n) for efficient prime check [OK]

Common Mistakes:

• Using i < n/2 instead of i <= n/2 in loop
• Wrong return type
• Incorrect boundary condition for n

5. You want to find all prime numbers between 10 and 20 using this function:

function isPrime(n: number): boolean {
  if (n <= 1) return false;
  for (let i = 2; i <= Math.sqrt(n); i++) {
    if (n % i === 0) return false;
  }
  return true;
}

Which of the following arrays correctly lists these primes?

medium

A. [10, 12, 14, 16, 18, 20]

B. [11, 13, 17, 19]

C. [11, 12, 13, 14, 15, 16, 17, 18, 19, 20]

D. [9, 11, 13, 15, 17, 19]

Solution

1. Step 1: Identify prime numbers between 10 and 20

   Check each number: 11 (prime), 12 (not), 13 (prime), 14 (not), 15 (not), 16 (not), 17 (prime), 18 (not), 19 (prime), 20 (not).

2. Step 2: List only primes in the array

   The primes are 11, 13, 17, and 19.

3. Final Answer:

   [11, 13, 17, 19] -> Option B

4. Quick Check:

   Primes 10-20 = [11,13,17,19] [OK]

Hint: Check each number with isPrime, collect true results [OK]

Common Mistakes:

• Including non-prime even numbers
• Including numbers less than 10 or greater than 20
• Confusing primes with odd numbers