JavaScript Program to Check Prime Number

Why This Matters

Checking if a number is prime is an essential concept in computer science and mathematics due to its applications in various fields such as cryptography, number theory, and algorithms. In this lesson, we will guide you through writing a JavaScript program to check for prime numbers, providing practical depth with real debugging mistakes from labs, original wordings, and more.

Core Concept

A prime number is a positive integer greater than 1 that has no positive divisors other than 1 and itself. For example, 2, 3, 5, 7, 11 are the first few prime numbers.

Here's a simple JavaScript program to check if a number is prime:

function isPrime(num) {
// Check base cases (1 and 0 are not prime)
if (num <= 1) return false;

// Check for divisibility by numbers up to the square root of the input number
for (let i = 2; i <= Math.sqrt(num); i++) {
if (num % i === 0) return false;
}

// If no divisors found, the number is prime
return true;
}

In this version of the code, we simplified the error handling to return false for incorrect inputs instead of throwing errors. This makes the function easier to use and test in various contexts.

Let's break this code down line by line:

1. function isPrime(num) - Defines a function called isPrime that takes an integer as an argument.
2. if (num <= 1) return false; - Checks if the input number is less than or equal to 1, and if so, returns false.
3. for (let i = 2; i <= Math.sqrt(num); i++) { ... } - Loops through all numbers from 2 up to the square root of the input number. This is an optimization, as we can stop checking divisors once we find one or reach the square root.
4. if (num % i === 0) return false; - Checks if the input number is divisible by the current loop variable i. If it is, the function returns false, indicating that the number is not prime.
5. return true; - If no divisors are found during the loop, the function returns true, indicating that the input number is a prime number.

Prerequisites

To understand this example, you should have the knowledge of the following JavaScript programming topics:

• Variables and data types
• Basic arithmetic operations
• Conditional statements (if...else)
• Loops (for loop)
• Math object functions (Math.sqrt())

Worked Example

Let's test our isPrime function with some examples:

console.log(isPrime(2)); // true
console.log(isPrime(4)); // false
console.log(isPrime(17)); // true
console.log(isPrime(97)); // true
console.log(isPrime(101)); // true

In this example, we call the isPrime function with various numbers and see that it correctly identifies prime numbers (2, 17, 97, 101) and non-prime numbers (4).

Common Mistakes

When writing a program to check for prime numbers, some common mistakes include:

Forgetting the base cases

Remember that 1 and 0 are not prime numbers. If you forget to handle these cases, your function will incorrectly classify them as primes.

Not checking divisibility up to the square root

Checking for divisors only up to the square root of the input number is an optimization, but it's essential to include this check in your program. If you omit it, your function may take too long to run or return incorrect results for large numbers.

Incorrectly handling even numbers

If a number is even and greater than 2, it cannot be prime unless it is 2 itself. This means that you should only check odd numbers as potential divisors when checking for primes. If you forget this rule, your function will incorrectly classify some even numbers (other than 2) as primes.

Practice Questions

1. Write a JavaScript program to find all prime numbers between 1 and 100 using the isPrime function we created.
2. Modify the isPrime function to handle negative numbers correctly, returning false for any negative input.
3. Optimize the isPrime function by skipping even numbers when checking divisors.
4. Write a JavaScript program to find the largest prime number less than 10^8 using the optimized isPrime function.
5. Add additional error handling to the isPrime function to catch edge cases like non-integer inputs or very large numbers that may cause issues during execution.
6. Investigate more efficient algorithms for checking prime numbers in JavaScript, such as the Sieve of Eratosthenes or Miller-Rabin primality tests. Research their time complexity and implementations in JavaScript.

FAQ

Why do we need to check divisibility up to the square root of the input number?

Checking for divisors only up to the square root of the input number is an optimization, as it allows us to stop checking divisors once we find one or reach the square root. This reduces the time complexity of our algorithm from O(n) to O(sqrt(n)).

Why can't we check for divisibility by 1 when verifying if a number is prime?

We don't need to check for divisibility by 1 because 1 is not considered a divisor. A prime number has no positive divisors other than 1 and itself, so checking for divisibility by 1 would always return true for prime numbers, which is redundant.

Can we optimize the isPrime function further to make it faster?

Yes, there are more efficient algorithms for checking prime numbers in JavaScript, such as the Sieve of Eratosthenes or Miller-Rabin primality tests. These algorithms have better time complexity and can be used to find prime numbers more efficiently. However, implementing these algorithms may require a deeper understanding of number theory and algorithms.