Skip to content

Instantly share code, notes, and snippets.

@khawajafarooq
Last active April 30, 2019 21:40
Show Gist options
  • Save khawajafarooq/762d9f21ef661baa9af86ba21f01795b to your computer and use it in GitHub Desktop.
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
/*
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)
@avirajkhare00
Copy link

This is wrong implementation.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment