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.

    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.

    Also popular now: