Check if Number is Prime in DSA Typescript

Mental Model

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

Analogy: Think of a prime number as a special kind of lock that only opens with two keys: 1 and the number itself.

Number: 7
Divisors: 1 -> 7
No other numbers fit exactly between 1 and 7

Dry Run Walkthrough

Input: Check if number 7 is prime

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

Step 1: Check if 7 is less than or equal to 1

7 (number to check)

Why: Numbers less than or equal to 1 are not prime

Step 2: Start checking divisors from 2 up to √7 (which is about 2.64)

Check divisor 2

Why: Only need to check up to square root to find divisors

Step 3: Check if 7 is divisible by 2

7 % 2 = 1 (not divisible)

Why: If divisible, 7 would not be prime

Step 4: No divisors found up to √7, conclude 7 is prime

7 is prime

Why: No divisor other than 1 and 7 found

Result:

7 is prime

Annotated Code

DSA Typescript

class PrimeChecker {
  static isPrime(num: number): boolean {
    if (num <= 1) return false; // numbers <= 1 are not prime
    const limit = Math.floor(Math.sqrt(num));
    for (let i = 2; i <= limit; i++) {
      if (num % i === 0) return false; // found a divisor, 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 <= 1) return false; // numbers <= 1 are not prime

Exclude numbers that cannot be prime

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

Calculate upper bound for divisor checks

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

Check all possible divisors from 2 to square root

if (num % i === 0) return false; // found a divisor, not prime

If divisible, number is not prime

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

If no divisors found, confirm 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: Naive approach checks all numbers up to n-1, which is O(n), so this method is faster

Edge Cases

number is 1

Returns false because 1 is not prime

DSA Typescript

if (num <= 1) return false; // numbers <= 1 are not prime

number is 2

Returns true because 2 is the smallest prime number

DSA Typescript

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

number is a large prime

Efficiently checks divisors only up to square root

DSA Typescript

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: Only check divisors up to the square root to improve efficiency

Mistake: Not handling numbers less than or equal to 1 correctly
Fix: Add a condition to return false for numbers <= 1

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 is prime.

Only divisors up to the square root need to be checked to confirm primality.

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