Last active
April 30, 2019 21:40
-
-
Save khawajafarooq/762d9f21ef661baa9af86ba21f01795b to your computer and use it in GitHub Desktop.
Sieve of Eratosthenes' method to find prime numbers up to a give number N
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes | |
The sieve of Eratosthenes is one of the most efficient way to find all prime numbers up to any given limit. | |
It's a simple and ancient algorithm that is know for it's performance. Here is a swift flavor of this algorithm. | |
*/ | |
func sieveOfEratosthenes(number n: UInt) -> [UInt] { | |
var list = Array(2...n) | |
list = list.filter { | |
// base case, if the value is equal to 2, 3 or 5 | |
if $0 == 2 || $0 == 3 || $0 == 5 { | |
return true | |
} | |
// if the value is not multiple of 2, 3 or 5 | |
else { | |
return $0 % 2 != 0 && $0 % 3 != 0 && $0 % 5 != 0 | |
} | |
} | |
return list | |
} | |
let primeNumbers = sieveOfEratosthenes(number: 100000) | |
print(primeNumbers) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
This is wrong implementation.