arrays - Swift使用eratosthenes方法获取素数

Question

我想使用 eratosthenes method

快速获取质数。我创建第一个函数来返回没有那些可以为特定乘数除以的数字的新数组，然后创建第二个函数来每次使用新的 P 乘数创建新数组。我想知道为什么它不起作用(看起来它以某种方式传递了旧数组，我不知道为什么)。它应该在末尾打印新的素数数组:

 var simpleArr : [Int] = []

for i in 2...100 {
    simpleArr.append(i)
}


func arrayEcludingDivingByP (p: Int, arrToCheck : [Int]) -> Array<Int>{

    var  tmp : [Int] = []

    for (ob, index) in arrToCheck.enumerated() {

        var isDividible : Bool = ob % p == 0 ? true : false

        if (!isDividible){
            tmp.append(ob)
        }
    }

    return tmp
}

var p : Int = 2


func getSimpleNumbersArrayFromArray (p : Int, arrPassed : [Int]) -> Array <Int>{

    var tmp : [Int] = []

    var newArr = arrayEcludingDivingByP(p: p, arrToCheck: arrPassed)

    if (newArr.isEmpty){
        // No more p availible, just return tmp

    }   else {
        let newP = p + 1
        getSimpleNumbersArrayFromArray(p: newP, arrPassed: newArr)
        tmp = newArr
        print("tmp array? \(tmp)")

    }

    return tmp


}

getSimpleNumbersArrayFromArray(p: p, arrPassed: simpleArr)

在控制台中打印:

tmp array? [1]
tmp array? [1, 2]
tmp array? [1, 2, 3]
tmp array? [1, 2, 3, 4]
tmp array? [1, 2, 3, 4, 5]
tmp array? [1, 2, 3, 4, 5, 6]
tmp array? [1, 2, 3, 4, 5, 6, 7]
tmp array? [1, 2, 3, 4, 5, 6, 7, 8]
tmp array? [1, 2, 3, 4, 5, 6, 7, 9, 10, 11]
tmp array? [1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13]
tmp array? [1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17]
tmp array? [1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19, 21, 22, 23]
tmp array? [1, 2, 3, 5, 6, 7, 9, 10, 11, 13, 14, 15, 17, 18, 19, 21, 22, 23, 25, 26, 27, 29, 30, 31]
tmp array? [1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20, 22, 23, 25, 26, 28, 29, 31, 32, 34, 35, 37, 38, 40, 41, 43, 44, 46, 47]
tmp array? [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, 87, 89, 91, 93, 95, 97]

但它假设打印最终迭代，其中 tmp 填充质数。我做错了什么？

Answer 1

您正在使用 newArr 来表示筛子中剩余的值。您的 tmp 数组应该是到目前为止找到的素数。此外，您正在使用令人困惑的递归调用。我建议简单地从 newArr 中获取第一个值，这是一个素数，将该素数添加到您的素数列表中，然后调用 arrayEcludingDividingByP 来过滤掉非素数可整除的由那个素数。重复直到 newArr isEmpty，这将在 条件绑定(bind) 语句 while let newP = newArr.first 失败并且循环结束时发生:

func getPrimes(arrPassed: [Int]) -> [Int] {
    var primes: [Int] = []
    var newArr = arrPassed

    while let newP = newArr.first {
        primes.append(newP)
        newArr = arrayEcludingDivingByP(p: newP, arrToCheck: newArr)
    }

    return primes
}

print(getPrimes(arrPassed: Array(2...100)))

这可以进一步优化，因为一旦 newP * newP 大于 newArr (newArr.last!) 中的最大数字，您就是完成后，您只需将 newArr 附加到 primes 并将 newArr 设置为 []。

此外，arrayEcludingDivingByP(p: newP, arrToCheck: newArr) 可以替换为 newArr.filter { $0 % newP != 0 }