问题描述
让我们看看我们想要找到 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.
这篇关于如何找到一个数作为素数之和?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!