Sieve of Eratosthenes Algorithms

sieve.swift

//: Playground - noun: a place where people can play

import UIKit

/* Sieve of Eratosthenes Algorithms
 *
 * In mathematics, the sieve of Eratosthenes one of a number of prime number sieves, is a simple, ancient algorithm
 * for finding all prime numbers up to any given limit.
 *
 * Pseudocode to find all the prime numbers less than or equal to a given integer n by Eratosthenes' method:
 *
 * 1. Create a list of consecutive integers from 2 through n: (2, 3, 4, ..., n).
 * 2. Initially, let p equal 2, the first prime number.
 * 3. Starting from p, enumerate its multiples by counting to n in increments of p, and mark them in the list.
 * 4. Find the first number greater than p in the list that is not marked. If there was no such number, stop. Otherwise,
 *    let p now equal this new number (which is the next prime), and repeat from step 3.
 *
 * When the algorithm terminates, the numbers remaining not marked in the list are all the primes below n.
 *
 * For more information see https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
 *
 */

// Mutating version, better performance
func primes(n: Int) ->[Int] {
    var numbers = [Int](2..<n)
    for i in 0..<n-2 {
        //guard let prime = numbers[i] where prime > 0 else { continue }
        let prime = numbers[i]
        if prime > 0 {
            for multiple in stride(from: 2 * prime-2, to: n-2, by: prime) {
                numbers[multiple] = 0
            }
        }
    }
    return numbers.filter {$0 > 0}
}

// Non-mutating version worst performance
func sieve(numbers: [Int]) -> [Int] {
    if numbers.isEmpty { return [] }
    let p = numbers[0]
    return [p] + sieve(numbers[1..<numbers.count].filter { $0 % p > 0 })
}

// TEST
let numbers = [Int](2..<21)
sieve(numbers)
primes(20)

let count = 10
let indices = [Int](count: count, repeatedValue: 1)





// Verify prime: trial division method
func isPrime(n: Int) -> Bool {
    // Special cases
    if n == 0 || n == 1 {
        return false
    }
    if n == 2 {
        return true
    }
    
    let limit = n-1
    //let limit = n/2
    //let limit = sqrt(Double(n))
    
    for var i = 2 ; i < limit ; i++ {
        if n % i == 0 {
            return false
        }
    }
    return true
}

isPrime(2)

// Find all prime numbers: trial division method

func findPrimes(n: Int) -> [Int] {
    var list = [Int]()
    
    for i in 2...n {
        if isPrime(i) {
          list.append(i)
        }
    }
    return list
}

var num = 20
primes(num)
findPrimes(num)