Java Coding Test Course, Finding Prime Numbers

1. Problem Definition

Many coding test problems require mathematical concepts or algorithmic thinking.
One of them is the problem of “Finding Prime Numbers.”
A prime number is defined as a natural number that has only two divisors: 1 and itself.
In other words, a prime number is a natural number greater than 1 that does not have any divisors other than 1 and itself.
For example, 2, 3, 5, 7, 11, 13, 17, etc., are prime numbers.

In this course, we will solve the problem of printing all prime numbers less than or equal to a given integer N.
Specifically, the problem becomes “Print all prime numbers less than or equal to the given integer N.”

2. Problem Example

Example Input: 20
Example Output: 2, 3, 5, 7, 11, 13, 17, 19

3. Algorithm Approach

There are several ways to find prime numbers.
The simplest method is to check each number from 2 to N to determine if it is prime.
However, this method is inefficient and has a time complexity of O(N^2).
Therefore, we will use a more efficient method, namely the Sieve of Eratosthenes algorithm.

3.1. Sieve of Eratosthenes Algorithm

The Sieve of Eratosthenes is a classical algorithm for finding prime numbers. The basic idea of this method is as follows:

List all numbers from 2 to N.
Select the smallest number, which is 2. Erase all multiples of 2.
Select the next smallest remaining number. This number is prime.
Erase all multiples of this number.
Repeat this process until there are no primes left among the numbers less than or equal to N.

4. Java Code Implementation

Now, let’s implement the Sieve of Eratosthenes algorithm in Java.
Below is the implementation code:


import java.util.ArrayList;
import java.util.List;

public class PrimeNumbers {
    public static void main(String[] args) {
        int N = 20; // Here, you can change the value of N to find primes in different ranges.
        List<Integer> primes = findPrimes(N);
        System.out.println("Primes (" + N + " or less): " + primes);
    }

    public static List<Integer> findPrimes(int N) {
        boolean[] isPrime = new boolean[N + 1];
        List<Integer> primes = new ArrayList<>();

        // Initialize false for 0 and 1 as they are not prime
        for (int i = 2; i <= N; i++) {
            isPrime[i] = true;
        }

        for (int i = 2; i * i <= N; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= N; j += i) {
                    isPrime[j] = false; // Exclude multiples of i from prime candidates
                }
            }
        }

        for (int i = 2; i <= N; i++) {
            if (isPrime[i]) {
                primes.add(i); // Add to the list of primes
            }
        }
        return primes;
    }
}

5. Code Explanation

The above code finds prime numbers through the following steps:

Array Initialization: It creates a boolean array called isPrime
to store whether numbers from 0 to N are prime. Initially, all numbers are assumed to be prime.
Prime Determination: It uses nested loops to erase multiples of each number. The outer loop represents the candidate prime numbers,
and the inner loop erases the multiples of the prime.
Prime List Generation: Finally, after determining the primes,
it checks the isPrime array to add actual prime numbers to the list.

6. Code Execution Result Explanation

When the above code is executed, it prints the list of prime numbers for the given value of N. For example, if N is 20, the output will be:
Primes (20 or less): [2, 3, 5, 7, 11, 13, 17, 19]

7. Performance Optimization

The Sieve of Eratosthenes algorithm has a time complexity of O(N log log N), making it very efficient.
However, when N is very large, memory usage must also be considered.
Therefore, here are some methods to save memory:

Since all even numbers except for 2 are not prime, we can search for primes only among odd numbers.
Instead of using an array, we can use a bit vector to reduce memory usage.
By exploiting symmetry, we only need to search up to the square root of N. That is, we can perform the work of identifying non-prime numbers only up to the square root,
as the remaining numbers will not be prime, so there is no need to store them.

8. Conclusion

In this course, we learned how to find prime numbers using Java.
The Sieve of Eratosthenes algorithm is extremely efficient for finding prime numbers,
and understanding such algorithms will be helpful in coding tests.
Additionally, understanding various data structures and algorithms, as well as basic mathematical facts that can assist in solving multiple high-level algorithm problems, is important.

In the next session, we will address a wider variety of algorithm problems.
I hope this will help you prepare for coding tests!