如何找到一个数作为素数之和? [英] How to find a number as a sum of prime numbers?

问题描述

让我们看看我们想要找到 1 到 1000 之间的所有数字，这些数字表示为两个素数之和.例如 8 = 3+5, 24 = 13+11

Lets see we want to find all numbers between 1 to 1000 which are represented as a sum of two prime numbers. e.g 8 = 3+5, 24 = 13+11

现在这可以通过迭代 1 到 1000 之间的素数列表在 O(n^2) 中完成.

Now this can be done in O(n^2) by iterating through the list of prime numbers between 1 to 1000.

有没有办法在小于 O(n^2) 的时间内做同样的事情.有没有一种方法可以在线性时间内做到这一点?

Is there anyway of doing the same thing in less than O(n^2).Is there a method for doing this in linear time ?

推荐答案

制作一个包含 1000 个布尔值的数组 p.如果 i 是质数，则将 p[i] 设置为 true，否则设置 false.

Make an array p of 1000 booleans. Set p[i] to true if i is prime, and false otherwise.

然后 O(N^2) 算法变得简单:在外循环中遍历数字 k 1 到 1000，然后遍历所有素数 x 大于 k 在内循环中，并检查是否存在质数使得 p[kx] 为 true:

Then the O(N^2) algorithm becomes easy: go through numbers k 1 through 1000 in the outer loop, then go through all primes x greater than k in an inner loop, and check if there exists a prime such that p[k-x] is true:

for k in 1..1000
    for x in primes greater than k
        if (p[x-k])
            print k can be represented as x plus (x-k)
            break

对于 1000 个数字的 O(N) 总运行时间，我怀疑能否在恒定时间内执行检查，因为计算机辅助验证目前以相当慢的速度进行.

I doubt that the check could be performed in constant time for a total running time of O(N) for the 1000 numbers, because computer-aided verification currently proceeds at a rather slow speeds.

这篇关于如何找到一个数作为素数之和?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！