Swift Coding Test Course, Finding Prime Numbers

Introduction

The programming language Swift is widely used for macOS and iOS application development.
The problem of finding prime numbers is often posed in algorithm tests for employment, and a sufficient understanding and practice of the solution methods are necessary.
In this article, we will take the algorithmic problem of determining prime numbers as an example and explain the solution process step by step.

Problem Description

Problem: Find all prime numbers less than or equal to the given integer N.

A simple definition of a prime number: A prime number is a natural number that has no divisors other than 1 and itself. That is, it can only be divided by 1 and N.
For example, 2, 3, 5, 7, 11, 13, 17, 19 are prime numbers.
The goal of this problem is to find all prime numbers less than or equal to the given input N and return them in the form of an array or list.

Implementation Plan

There are several approaches to finding prime numbers, but here we will discuss how to find primes using the Sieve of Eratosthenes algorithm.
This method can efficiently find prime numbers with a time complexity of O(N log log N).

Step 1: Initialize the Array

First, create a boolean array of size N+1 to initialize whether each index is a prime number.
All indexes are initialized to true, while indexes 0 and 1 are set to false.

Step 2: Determine Primes

Starting from 2, check each number.
If the current number is determined to be prime, set all its multiples to false.
Repeat this process up to the square root of N.

Step 3: Output Primes

Finally, all indexes that remain true are prime numbers.
Use these indexes to output the result list.

Swift Code Implementation

        
        func sieveOfEratosthenes(n: Int) -> [Int] {
            // Initialize an array of size N+1
            var isPrime = [Bool](repeating: true, count: n + 1)
            isPrime[0] = false // 0 is not prime
            isPrime[1] = false // 1 is not prime

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

            // Generate the list of primes
            var primes: [Int] = []
            for i in 2...n {
                if isPrime[i] {
                    primes.append(i)
                }
            }
            
            return primes
        }

        // Example execution
        let n = 30
        let primesUnderN = sieveOfEratosthenes(n: n)
        print("Primes:", primesUnderN)
        
        

Code Explanation

The Swift code above implements a method for finding prime numbers less than or equal to a given N.
The function func sieveOfEratosthenes takes an integer N as input and executes the following steps:

1. Array Initialization: Create a boolean array of size N+1 and set all values to true.
2. Prime Determination: Starting from 2, determine all primes and set their multiples to false.
3. Output Primes: Check the final array and return all indexes that remain true in list form.

Example Execution

When N = 30, executing the above code produces the following result:

        
        Primes: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
        
        

Conclusion

Calculating prime numbers can be an important topic in learning programming and is often asked in interviews.
By using the Sieve of Eratosthenes algorithm, we can efficiently find prime numbers.
Refer to the methods and code explained in this article and try testing with various input values.
Finding prime numbers is a good way to practice algorithms and can serve as a foundation for solving more complex problems.