{"id":33404,"date":"2024-11-01T09:16:12","date_gmt":"2024-11-01T09:16:12","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=33404"},"modified":"2024-11-01T11:38:50","modified_gmt":"2024-11-01T11:38:50","slug":"java-coding-test-course-finding-prime-numbers","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/33404\/","title":{"rendered":"Java Coding Test Course, Finding Prime Numbers"},"content":{"rendered":"

<\/p>\n

\n
\n

1. Problem Definition<\/h2>\n

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

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

2. Problem Example<\/h2>\n

\nExample Input:<\/strong> 20<\/code>
\nExample Output:<\/strong> 2, 3, 5, 7, 11, 13, 17, 19<\/code>\n<\/p>\n

3. Algorithm Approach<\/h2>\n

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

3.1. Sieve of Eratosthenes Algorithm<\/h3>\n

\n The Sieve of Eratosthenes is a classical algorithm for finding prime numbers. The basic idea of this method is as follows:\n <\/p>\n

    \n
  1. List all numbers from 2 to N.<\/li>\n
  2. Select the smallest number, which is 2. Erase all multiples of 2.<\/li>\n
  3. Select the next smallest remaining number. This number is prime.<\/li>\n
  4. Erase all multiples of this number.<\/li>\n
  5. Repeat this process until there are no primes left among the numbers less than or equal to N.<\/li>\n<\/ol>\n

    4. Java Code Implementation<\/h2>\n

    \n Now, let\u2019s implement the Sieve of Eratosthenes algorithm in Java.
    \n Below is the implementation code:\n <\/p>\n

    \nimport java.util.ArrayList;\nimport java.util.List;\n\npublic class PrimeNumbers {\n    public static void main(String[] args) {\n        int N = 20; \/\/ Here, you can change the value of N to find primes in different ranges.\n        List<Integer> primes = findPrimes(N);\n        System.out.println(\"Primes (\" + N + \" or less): \" + primes);\n    }\n\n    public static List<Integer> findPrimes(int N) {\n        boolean[] isPrime = new boolean[N + 1];\n        List<Integer> primes = new ArrayList<>();\n\n        \/\/ Initialize false for 0 and 1 as they are not prime\n        for (int i = 2; i <= N; i++) {\n            isPrime[i] = true;\n        }\n\n        for (int i = 2; i * i <= N; i++) {\n            if (isPrime[i]) {\n                for (int j = i * i; j <= N; j += i) {\n                    isPrime[j] = false; \/\/ Exclude multiples of i from prime candidates\n                }\n            }\n        }\n\n        for (int i = 2; i <= N; i++) {\n            if (isPrime[i]) {\n                primes.add(i); \/\/ Add to the list of primes\n            }\n        }\n        return primes;\n    }\n}\n            <\/code><\/pre>\n
    5. Code Explanation<\/h2>\n
    \n                The above code finds prime numbers through the following steps:\n            <\/p>\n