JavaScript Coding Test Course, Finding Prime Numbers

Hello! Today we will discuss the ‘Finding Prime Numbers’ problem, which frequently appears in JavaScript coding tests. A prime number is a natural number greater than 1 that cannot be formed by multiplying two smaller natural numbers. For example, 2, 3, 5, 7, and 11 are all prime numbers. In this article, we will implement an algorithm to find prime numbers and explain the process in detail.

1. Problem Definition

Given an integer N, write a program that outputs all prime numbers less than or equal to N.

Input: An integer N (1 ≤ N ≤ 10,000)

Output: Print all prime numbers less than or equal to N in a single line

2. Algorithm Selection

The representative algorithm to find prime numbers is the Sieve of Eratosthenes. This algorithm is very efficient and suitable for finding prime numbers less than or equal to N. The reasons for using this algorithm are as follows:

  • It has a time complexity of O(N log log N), making it very fast.
  • The memory usage is moderate, allowing it to handle up to N = 10,000 smoothly.

2.1 Explanation of the Sieve of Eratosthenes Algorithm

The Sieve of Eratosthenes algorithm proceeds through the following steps:

  1. Add all numbers from 2 to N to a list.
  2. Confirm the first number in the list, which is 2, as a prime. Remove all multiples of 2 from the list.
  3. Confirm the next number (3) as a prime and remove all multiples of 3. Repeat this process.
  4. Continue only while the current number is less than or equal to the square root of N.

3. Writing Code

Now, let’s write the code in JavaScript based on the above algorithm.

function sieveOfEratosthenes(N) {
    const primes = [];
    const isPrime = new Array(N + 1).fill(true);
    isPrime[0] = isPrime[1] = false; // 0 and 1 are not prime numbers.

    for (let i = 2; i <= N; i++) {
        if (isPrime[i]) {
            primes.push(i); // i is a prime number.
            for (let j = i * 2; j <= N; j += i) {
                isPrime[j] = false; // Multiples of i are not prime numbers.
            }
        }
    }
    return primes;
}

// Example of usage
const N = 100; // Input N.
const primeNumbers = sieveOfEratosthenes(N);
console.log(primeNumbers.join(' ')); // Output the prime numbers.

4. Code Analysis

Let’s take a look at the written code step by step:

  • const isPrime = new Array(N + 1).fill(true);: This creates an array of numbers up to N and initializes all values to true.
  • isPrime[0] = isPrime[1] = false;: Since 0 and 1 are not prime, they are set to false.
  • The for loop checks the numbers from 2 to N. If isPrime[i] is true, it means i is a prime number. Add this number to the primes array.
  • Also, iterate through all multiples of i and set them to false.
  • Through this process, the final array containing only prime numbers is returned.

5. Test Cases

Now, let’s run some test cases to verify that our implementation works well.

console.log(sieveOfEratosthenes(10)); // [2, 3, 5, 7]
console.log(sieveOfEratosthenes(50)); // [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
console.log(sieveOfEratosthenes(100)); // [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

6. Conclusion

Today we learned how to find prime numbers in JavaScript. We explored an efficient method of locating primes using the Sieve of Eratosthenes, and based on that, we wrote practical code. I hope this code helps enhance your algorithm skills further. Additionally, I hope it aids you in preparing for coding tests!

7. Additional Learning Resources

If you want to see more materials and solve problems, please refer to the following resources:

  • LeetCode – Various algorithm problems and solutions
  • HackerRank – Coding test problems and practices
  • Codewars – Coding practice by solving problems in various languages