Prime Number in O(n) Time Complexity using JavaScript

Given a non-negative integer n check if it is a prime number

Prime numbers are positive numbers greater than 1 that are divisible only by 1 and the number itself.

Examples of prime numbers: 2, 3, 5, 7, 11, 13, 17, 19, 23

Example 1:

Input: n = 31
Output: true

Example 2:

Input: n = 6
Output: false
Explanation: 6 is divisible by 2 and 3.

Note:

Your algorithm should run in O(n) time and use O(1) space.

Understanding the Problem

The core challenge of this problem is to determine if a given number n is a prime number. Prime numbers have significant applications in fields such as cryptography, number theory, and computer science. A common misconception is that checking for prime numbers requires checking divisibility by all numbers up to n, but there are more efficient methods.

Approach

To solve this problem, we can start with a naive approach and then optimize it:

Naive Solution

The naive solution involves checking if n is divisible by any number from 2 to n-1. If we find any such divisor, n is not prime.

function isPrime(n) {
  if (n <= 1) return false; // 0 and 1 are not prime numbers
  for (let i = 2; i < n; i++) {
    if (n % i === 0) return false; // Found a divisor
  }
  return true; // No divisors found, n is prime
}

This solution has a time complexity of O(n) and space complexity of O(1). However, it can be optimized further.

Optimized Solution

We can improve the efficiency by only checking divisors up to the square root of n. If n is divisible by any number greater than its square root, it must also be divisible by a number smaller than its square root.

function isPrime(n) {
  if (n <= 1) return false; // 0 and 1 are not prime numbers
  if (n <= 3) return true; // 2 and 3 are prime numbers
  if (n % 2 === 0 || n % 3 === 0) return false; // Eliminate multiples of 2 and 3

  for (let i = 5; i * i <= n; i += 6) {
    if (n % i === 0 || n % (i + 2) === 0) return false; // Check for divisors
  }
  return true; // No divisors found, n is prime
}

This optimized solution has a time complexity of O(√n) and space complexity of O(1).

Algorithm

Let's break down the optimized algorithm step-by-step:

Check if n is less than or equal to 1. If so, return false.
Check if n is 2 or 3. If so, return true.
Check if n is divisible by 2 or 3. If so, return false.
Iterate from 5 to the square root of n, incrementing by 6 each time. For each iteration, check if n is divisible by i or i + 2. If so, return false.
If no divisors are found, return true.

Code Implementation

Here is the JavaScript implementation of the optimized solution:

function isPrime(n) {
  if (n <= 1) return false; // 0 and 1 are not prime numbers
  if (n <= 3) return true; // 2 and 3 are prime numbers
  if (n % 2 === 0 || n % 3 === 0) return false; // Eliminate multiples of 2 and 3

  for (let i = 5; i * i <= n; i += 6) {
    if (n % i === 0 || n % (i + 2) === 0) return false; // Check for divisors
  }
  return true; // No divisors found, n is prime
}

Complexity Analysis

The time complexity of the optimized solution is O(√n) because we only iterate up to the square root of n. The space complexity remains O(1) as we are not using any additional space.

Edge Cases

Consider the following edge cases:

n = 0: Should return false.
n = 1: Should return false.
n = 2: Should return true.
n = 3: Should return true.
n = 4: Should return false.

Testing

To test the solution comprehensively, consider a variety of test cases:

console.log(isPrime(0)); // false
console.log(isPrime(1)); // false
console.log(isPrime(2)); // true
console.log(isPrime(3)); // true
console.log(isPrime(4)); // false
console.log(isPrime(31)); // true
console.log(isPrime(37)); // true
console.log(isPrime(49)); // false

Thinking and Problem-Solving Tips

When approaching such problems, consider the following tips:

Understand the problem requirements and constraints.
Start with a naive solution and then look for optimizations.
Break down the problem into smaller, manageable parts.
Consider edge cases and test your solution thoroughly.

Conclusion

In this blog post, we discussed how to determine if a number is prime using an optimized algorithm with a time complexity of O(√n). Understanding and solving such problems is crucial for developing strong problem-solving skills in computer science and programming.

Additional Resources

For further reading and practice, consider the following resources: