只是为了澄清,这不是一个功课问题:)
我想找到我正在建造的数学应用程序的素数并且遇到了Eratosthenes的Sieve方法.
我用Python编写了它的实现.但它非常慢.比方说,如果我想找到不到200万的所有素数.大约需要20分钟.(此时我停了下来).我怎样才能加快速度呢？
def primes_sieve(limit):
limitn = limit+1
primes = range(2, limitn)
for i in primes:
factors = range(i, limitn, i)
for f in factors[1:]:
if f in primes:
primes.remove(f)
return primes
print primes_sieve(2000)
更新: 我最终对这段代码进行了分析,发现花了很多时间从列表中删除一个元素.考虑到它必须遍历整个列表(最坏情况)才能找到元素然后将其删除然后重新调整列表(可能还有一些副本继续？),这是相当容易理解的.无论如何,我把字典列表删掉了.我的新实施 -
def primes_sieve1(limit):
limitn = limit+1
primes = dict()
for i in range(2, limitn): primes[i] = True
for i in primes:
factors = range(i,limitn, i)
for f in factors[1:]:
primes[f] = False
return [i for i in primes if primes[i]==True]
print primes_sieve1(2000000)
这不是作业,我只是好奇.
INFINITE是这里的关键词.
我希望在primes()中使用它作为p.我相信这是Haskell中的内置函数.
所以,答案不能像"Just do a Sieve"那样天真.
首先,您不知道将消耗多少连续素数.好吧,假设你可以一次编制100个.您是否会使用相同的Sieve方法以及素数公式的频率？
我更喜欢非并发方法.
感谢您阅读(和写作;))!
我无法理解这段代码:
let
sieve (p:xs) = p : sieve (filter (\ x -> x `mod` p /= 0) xs)
in sieve [2 .. ]
有人可以为我分手吗？我知道它有递归,但这就是问题我无法理解这个例子中的递归是如何工作的.
我写了一个函数,使用流无限期地生成质数(维基百科:Erastothenes的增量筛).它返回一个流,但它也在内部合并素数倍流以标记即将到来的复合.如果我自己这样说,这个定义简洁,实用,优雅且易于理解:
def primes(): Stream[Int] = {
def merge(a: Stream[Int], b: Stream[Int]): Stream[Int] = {
def next = a.head min b.head
Stream.cons(next, merge(if (a.head == next) a.tail else a,
if (b.head == next) b.tail else b))
}
def test(n: Int, compositeStream: Stream[Int]): Stream[Int] = {
if (n == compositeStream.head) test(n+1, compositeStream.tail)
else Stream.cons(n, test(n+1, merge(compositeStream, Stream.from(n*n, n))))
}
test(2, Stream.from(4, 2))
}
但是,当我尝试生成第1000个素数时,我得到了"java.lang.OutOfMemoryError:超出GC开销限制".
我有一个替代解决方案,它在primes上返回一个迭代器,并在内部使用元组的优先级队列(multiple,prime用于生成多个)来标记即将到来的复合.它运行良好,但它需要大约两倍的代码,我基本上不得不从头重新开始:
import scala.collection.mutable.PriorityQueue
def primes(): Iterator[Int] = {
// Tuple (composite, prime) is used to generate …