Kotlin coding test course, finding prime numbers

In this section, we will study various problems necessary to enhance coding skills and learn about the algorithm for finding prime numbers. A prime number is a natural number that can only be divided by 1 and itself. Prime numbers play an important role in mathematics and frequently appear in various algorithm problems. Learning efficient algorithms to solve these problems is a great help in preparing for coding interviews.

Problem Description

Write an algorithm to find all prime numbers that are less than or equal to the given natural number N.

Input

  • Natural number N (2 ≤ N ≤ 100,000)

Output

  • Print all prime numbers less than or equal to N in one line, separated by spaces.

Approach to the Problem

There are several methods to find prime numbers, but here we will use the Sieve of Eratosthenes algorithm. This algorithm is one of the most efficient ways to find all prime numbers within a given range. In particular, it is very efficient with a time complexity of O(n log log n), making it suitable for finding large prime numbers.

What is the Sieve of Eratosthenes?

The Sieve of Eratosthenes proceeds through the following steps:

  1. List all natural numbers from 2 to N.
  2. Since 2 is prime, remove all of its multiples (4, 6, 8, …).
  3. Next, consider the smallest remaining number (3) as prime, and remove all of its multiples (6, 9, …).
  4. Repeat this process up to the square root of N, and all remaining numbers are prime.

Code Implementation

Kotlin Code


fun sieveOfEratosthenes(n: Int): List {
    val isPrime = BooleanArray(n + 1) { true }
    isPrime[0] = false // 0 is not prime
    isPrime[1] = false // 1 is not prime

    for (i in 2..Math.sqrt(n.toDouble()).toInt()) {
        if (isPrime[i]) {
            for (j in i * i..n step i) {
                isPrime[j] = false // multiples of i are not prime
            }
        }
    }

    return (2..n).filter { isPrime[it] } // return list of primes
}

fun main() {
    val n = readLine()!!.toInt()
    val primes = sieveOfEratosthenes(n)
    println(primes.joinToString(" ")) // print primes
}

Code Explanation

The above code implements the Sieve of Eratosthenes algorithm using Kotlin. Now, let’s take a look at each part:

  • BooleanArray(n + 1) { true }: Initializes all numbers up to N as prime.
  • isPrime[0] = false and isPrime[1] = false: Set 0 and 1 as false because they are not prime.
  • Math.sqrt(n.toDouble()).toInt(): Iterates up to the square root of N to check for primes.
  • for (j in i * i..n step i): Loop to set multiples of prime i to false.
  • (2..n).filter { isPrime[it] }: Finally returns the list of primes.

Algorithm Analysis

The time complexity of this algorithm is O(n log log n). This is very efficient for the problem of finding prime numbers. The space complexity is O(n). Using this algorithm, prime numbers up to 100,000 can be found very quickly.

Test Cases

Now let’s look at some test cases to verify that the algorithm works correctly.

Test Case 1

  • Input: 10
  • Output: 2 3 5 7

Test Case 2

  • Input: 30
  • Output: 2 3 5 7 11 13 17 19 23 29

Test Case 3

  • Input: 1
  • Output: (no output)

Conclusion

In this tutorial, we used the Sieve of Eratosthenes algorithm to find prime numbers. This algorithm is a common problem in coding tests, so it is essential to master it. Understanding each step of the algorithm carefully and testing it against various input values to validate its effectiveness is important.

In the future, we will cover various coding test problems using Kotlin. Continue learning, and focus on understanding the efficiency and functioning principles of each algorithm. Happy coding!