Check if Number is Prime in DSA Typescript - Time & Space Complexity

Time Complexity: Check if Number is Prime

O(√n)

Understanding Time Complexity

We want to understand how the time to check if a number is prime grows as the number gets bigger.

How many steps does it take to decide if a number has no divisors other than 1 and itself?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

This code checks if a number is prime by testing divisors from 2 up to the square root of the number.

Identify Repeating Operations

• Primary operation: The for-loop checking divisors from 2 to √num.
• How many times: Approximately √n times, where n is the input number.

How Execution Grows With Input

As the number gets bigger, the number of checks grows roughly with the square root of that number.

Input Size (n)	Approx. Operations
10	About 3 checks (2, 3)
100	About 10 checks (2 to 10)
1000	About 31 checks (2 to 31)

Pattern observation: The number of steps grows slower than the number itself, roughly like the square root.

Final Time Complexity

Time Complexity: O(√n)

This means the time to check if a number is prime grows roughly with the square root of the number.

Common Mistake

[X] Wrong: "We need to check all numbers up to n-1 to find if a number is prime."

[OK] Correct: Checking beyond the square root is unnecessary because any larger factor pairs with a smaller one already checked.

Interview Connect

Understanding this time complexity helps you explain efficient prime checks and shows you can optimize simple loops, a skill valued in interviews.

Self-Check

"What if we checked divisors only up to n/2 instead of √n? How would the time complexity change?"

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