Check if Number is Prime in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a prime number?

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

intermediate

Why do we only check divisors up to the square root of a number when testing for primality?

Because if a number has a divisor larger than its square root, it must also have a smaller divisor below the square root. So checking up to the square root is enough to find any divisor.

beginner

What is the first step in checking if a number is prime?

Check if the number is less than or equal to 1. If yes, it is not prime.

beginner

In TypeScript, how do you write a loop to check divisors from 2 up to the square root of a number 'n'?

for (let i = 2; i <= Math.sqrt(n); i++) { /* check if n % i === 0 */ }

beginner

What does it mean if a number 'n' is divisible by some number 'i' other than 1 and itself?

It means 'n' is not a prime number because it has a divisor other than 1 and itself.

Which number is NOT a prime number?

A 2

B 3

C 4

D 5

4 is divisible by 2, so it is not prime.

What is the smallest prime number?

A 3

B 1

C 0

D 2

2 is the smallest prime number because it is greater than 1 and only divisible by 1 and itself.

Why do we skip checking divisibility by 1 when testing if a number is prime?

A Because 1 divides every number

B Because 1 is not a number

C Because 1 is prime

D Because 1 is even

1 divides every number, so it does not help to check for primality.

If a number 'n' is divisible by 7, what can we say about 'n'?

A n is prime

B n is not prime

C n is 7

D n is less than 7

If 'n' has a divisor other than 1 and itself (like 7), it is not prime.

What is the time complexity of checking if a number 'n' is prime using the square root method?

A O(√n)

B O(log n)

C O(n)

D O(n^2)

Checking divisors up to the square root of 'n' takes O(√n) time.

Explain step-by-step how to check if a number is prime.

Think about divisors and the range to check.

Why is checking divisors only up to the square root enough to determine if a number is prime?

Consider pairs of factors.

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