
Swift: Sieve of Eratosthenes
This will be a very small publication, which I was inspired by this article. No, I'm not going to compete with the solution proposed there (except in brevity), but maybe, as a demonstration of Swift's capabilities, it will be interesting to the habrasociety.
The solution absolutely repeats the algorithm described in Wikipedia , without any modifications.
Those interested can play around with this in this sandbox. The maximum that I managed to squeeze there - in the region of 8,500,000, the search takes about 6 seconds. Unfortunately, running this code in the playground on my Mac Mini Late 2014 (Core i5, 8 GB) already with the max = 1,000,000 parameter leads to wild brakes, so be careful. On the link above, everything spins much faster.
The solution absolutely repeats the algorithm described in Wikipedia , without any modifications.
import Foundation
// квадрат числа
extension Int {
func powerOf2() -> Int {
return self * self
}
}
// до скольки считаем?
let max = 8_500_000
// первое простое число
var testValue = 2
let startTime = Date()
// заполняем массив
var data = (2...max).map{$0}
let allocationTime = Date()
// вычисления
while (testValue.powerOf2() <= max) {
data.removeAll(where: {$0 >= testValue.powerOf2() && $0.isMultiple(of: testValue)})
testValue = data.first(where: {$0 > testValue})!
}
let overallTime = Date()
// выводим результаты
print("Всего \(data.count) простых чисел: ", data)
print()
print("Выделение массива: \(String(format: "%.2f",(allocationTime.timeIntervalSince(startTime)))) с. ")
print("Вычисления: \(String(format: "%.2f",(overallTime.timeIntervalSince(allocationTime)))) с. ")
print("Всего: \(String(format: "%.2f",(overallTime.timeIntervalSince(startTime)))) с. ")
Those interested can play around with this in this sandbox. The maximum that I managed to squeeze there - in the region of 8,500,000, the search takes about 6 seconds. Unfortunately, running this code in the playground on my Mac Mini Late 2014 (Core i5, 8 GB) already with the max = 1,000,000 parameter leads to wild brakes, so be careful. On the link above, everything spins much faster.