加速质数生成

Question

我写了一个生成素数的程序。它运行良好，但我想加快它的速度，因为生成所有质数直到 10000 需要相当长的时间

var list = [2,3]
var limitation = 10000
var flag = true
var tmp = 0

for (var count = 4 ; count <= limitation ; count += 1 ){


    while(flag && tmp <= list.count - 1){
        if (count % list[tmp] == 0){
            flag = false

        }else if ( count % list[tmp] != 0 && tmp != list.count - 1  ){
            tmp += 1
        }else if ( count % list[tmp] != 0 && tmp == list.count - 1  ){
            list.append(count)

        }
    }
flag = true
tmp = 0
}

print(list)

Answer 1

两个简单的改进将使它快速达到 100,000 甚至 1,000,000。

除 2 以外的所有素数都是奇数

从5开始循环，每次递增2。这不会加快很多速度，因为您在第一次尝试时就找到了反例，但它仍然是一个非常典型的改进。

仅搜索您正在测试的值的平方根

平方根是你将因子减半的点space，即任何小于平方根的因子都与大于平方根的因子配对，所以你只需要检查上面或在它下面。平方根以下的数字要少得多，因此您应该只检查小于或等于平方根的值。

以10000为例。平方根是 100。为此，您只需查看小于平方根的值，就素数而言，它大约是 25 个值，而不是对所有小于 10,000 的素数进行超过 1000 次检查。

做得更快

尝试另一种方法，例如 sieve。这些方法速度更快，但内存开销更高。

Answer 2

除了 Nick 已经解释过的内容，您还可以轻松利用以下内容属性：所有大于 3 的素数都等于 1 或 -1 mod 6.

因为您已经在初始列表中包含了 2 和 3，因此您可以从 count = 6 开始，测试 count - 1 和 count + 1，每次递增 6。

以下是我在 Swift 上的第一次尝试，所以请原谅语法可能远非最佳。

var list = [2,3]
var limitation = 10000
var flag = true
var tmp = 0
var max = 0

for(var count = 6 ; count <= limitation ; count += 6) {
  for(var d = -1; d <= 1; d += 2) {
    max = Int(floor(sqrt(Double(count + d))))

    for(flag = true, tmp = 0; flag && list[tmp] <= max; tmp++) {
      if((count + d) % list[tmp] == 0) {
        flag = false
      }
    }
    if(flag) {
      list.append(count + d)
    }
  }
}
print(list)

我已经在 iswift.org/playground 上测试了上面的代码，限制为 10,000、100,000 和 1,000,000。

加速质数生成

speed up prime number generating

primes

swift

除 2 以外的所有素数都是奇数

仅搜索您正在测试的值的平方根

做得更快