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.<\/p>\n
Write an algorithm to find all prime numbers that are less than or equal to the given natural number N.<\/p>\n
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.<\/p>\n
The Sieve of Eratosthenes proceeds through the following steps:<\/p>\n
\nfun sieveOfEratosthenes(n: Int): List {\n val isPrime = BooleanArray(n + 1) { true }\n isPrime[0] = false \/\/ 0 is not prime\n isPrime[1] = false \/\/ 1 is not prime\n\n for (i in 2..Math.sqrt(n.toDouble()).toInt()) {\n if (isPrime[i]) {\n for (j in i * i..n step i) {\n isPrime[j] = false \/\/ multiples of i are not prime\n }\n }\n }\n\n return (2..n).filter { isPrime[it] } \/\/ return list of primes\n}\n\nfun main() {\n val n = readLine()!!.toInt()\n val primes = sieveOfEratosthenes(n)\n println(primes.joinToString(\" \")) \/\/ print primes\n}\n <\/int><\/code><\/pre>\nCode Explanation<\/h3>\n
The above code implements the Sieve of Eratosthenes algorithm using Kotlin. Now, let’s take a look at each part:<\/p>\n
\nBooleanArray(n + 1) { true }<\/code>: Initializes all numbers up to N as prime.<\/li>\nisPrime[0] = false<\/code> and isPrime[1] = false<\/code>: Set 0 and 1 as false because they are not prime.<\/li>\nMath.sqrt(n.toDouble()).toInt()<\/code>: Iterates up to the square root of N to check for primes.<\/li>\nfor (j in i * i..n step i)<\/code>: Loop to set multiples of prime i to false.<\/li>\n(2..n).filter { isPrime[it] }<\/code>: Finally returns the list of primes.<\/li>\n<\/ul>\nAlgorithm Analysis<\/h2>\n
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.<\/p>\n
Test Cases<\/h2>\n
Now let’s look at some test cases to verify that the algorithm works correctly.<\/p>\n
Test Case 1<\/h3>\n