Swift Coding Test Course, Finding Amazing Prime Numbers

Learning the programming language Swift is an exciting experience for many developers. In this course, we will address the ‘prime number’ problem, which often appears in coding tests, and explore step-by-step how to solve it using Swift. We will explain this through the problem of ‘Finding Amazing Primes.’

Problem Description

Given an integer N (1 ≤ N ≤ 10000), print all prime numbers between 1 and N.

What is a Prime Number?

A prime number is a natural number greater than 1 that has no divisors other than 1 and itself. For example, 2, 3, 5, and 7 are all prime numbers. In contrast, 4, 6, 8, and 9 are not prime numbers.

Approach to the Problem

To solve this problem, we will use the algorithm known as the Sieve of Eratosthenes, which is one of the methods for finding prime numbers. This algorithm is an efficient way to find all primes within a given range of numbers.

Sieve of Eratosthenes Algorithm

  1. Create a list containing all integers from 1 to N.
  2. Starting from 2, remove all multiples of the current number from the list.
  3. Continue repeating the above process with the next remaining number in the list.
  4. After processing all numbers up to N, the numbers remaining in the list are prime.

Implementation in Swift

Now let’s implement this algorithm in Swift. The following code shows how to print all prime numbers for a given N:


func findPrimes(upTo n: Int) -> [Int] {
    guard n >= 2 else { return [] }

    var isPrime = [Bool](repeating: true, count: n + 1)
    isPrime[0] = false
    isPrime[1] = false

    for i in 2...Int(sqrt(Double(n))) {
        if isPrime[i] {
            for j in stride(from: i * i, through: n, by: i) {
                isPrime[j] = false
            }
        }
    }

    return isPrime.enumerated().compactMap { $0.element ? $0.offset : nil }
}

// Example usage
let n = 100
let primes = findPrimes(upTo: n)
print("Prime numbers from 1 to \(n) are: \(primes)")

Code Explanation

The code above works as follows:

  1. The function findPrimes takes an argument n and finds prime numbers from 1 to n.
  2. An array isPrime is created, initializing all indices as prime. Indices 0 and 1 are set to false as they are not prime.
  3. For all numbers from 2 to sqrt(n), if the current number is prime, its multiples are removed from the list.
  4. The remaining elements in the list are printed.

Testing and Results

Now let’s execute the code and check the results. For example, when n = 100, the output should be as follows:


Prime numbers from 1 to 100 are: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

Time Complexity

The Sieve of Eratosthenes algorithm has an average time complexity of O(n log log n). This is one of the effective methods for finding prime numbers, becoming significantly faster as n increases.

Conclusion

In this course, we addressed the algorithm for finding prime numbers using Swift. By solving these basic algorithm problems, you can enhance your coding skills and improve your ability to solve more complex problems. During the problem-solving process, try applying various algorithms and programming concepts.

If you want to learn more source code and algorithms, stay tuned for the next course!