Java Coding Test Course, Finding Amazing Primes

Many people preparing for coding tests struggle with the difficulty and complexity of algorithm problems. Today, through a problem titled “Finding Interesting Primes,” we will introduce various algorithms for finding primes (premium numbers) and see how to efficiently solve the problem using Java.

Problem Description

Write a function to find all primes less than or equal to a given number N. Here, a prime is defined as a natural number that has no divisors other than 1 and itself.

Input: A natural number N is given on the first line. (2 ≤ N ≤ 1000)

Output: Print all primes less than or equal to N on one line, separated by spaces.

Example

Input: 
10

Output: 
2 3 5 7

Understanding and Analyzing the Problem

To solve the above problem, it is essential to understand the definition of a prime and basic methods for finding primes. A prime is a number that cannot be divided by natural numbers other than 1 and itself, so we can efficiently find primes using division operations.

However, simply checking all numbers from 1 to N is inefficient, with a time complexity of O(N^2). Therefore, a more efficient algorithm is needed. We can efficiently find primes using the Sieve of Eratosthenes algorithm.

Sieve of Eratosthenes

This algorithm works as follows:

  1. Prepare a list of all natural numbers from 2 to N.
  2. Select the first number in the list (2) and remove all its multiples.
  3. Select the next remaining number (3) and remove its multiples.
  4. Repeat this process until all numbers less than or equal to N have been removed. The remaining numbers are all primes.

Java Code Implementation

Now we will implement the above algorithm in Java.


public class PrimeSieve {
    public static void main(String[] args) {
        int N = 10; // The number N to use
        boolean[] isPrime = new boolean[N + 1];
        
        // Initialization
        for (int i = 2; i <= N; i++) {
            isPrime[i] = true;
        }

        // Sieve of Eratosthenes
        for (int i = 2; i * i <= N; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= N; j += i) {
                    isPrime[j] = false;
                }
            }
        }

        // Output results
        for (int i = 2; i <= N; i++) {
            if (isPrime[i]) {
                System.out.print(i + " ");
            }
        }
    }
}

Explanation

The code above goes through the following steps:

  1. First, it takes the input N and initializes a boolean array for numbers from 2 to N. Each index in the array indicates whether the corresponding number is prime.
  2. Then, it applies the Sieve of Eratosthenes algorithm to mark the indexes of non-prime numbers as false.
  3. Finally, it iterates through the isPrime array, printing indexes that are true to list the primes.

Time Complexity

The time complexity of this algorithm is O(N log(log(N))), which operates efficiently even for large N. This is significantly more efficient than simply dividing all numbers.

Conclusion

In this lesson, we implemented the Sieve of Eratosthenes algorithm in Java to find primes. Familiarity with such basic algorithms can help you score higher when solving various algorithm problems in coding tests. Furthermore, remember that in coding tests, both the readability and optimization of your code are also important scoring factors, so it is necessary to keep this in mind when coding.

Let's continue working on various algorithm problems together to improve our skills!