我是编程世界的新手.我只是在python中编写这段代码来生成N个素数.用户应输入N的值,即打印出的素数总数.我写了这段代码,但它没有抛出所需的输出.相反,它打印素数直到第N个数字.例如:用户输入N = 7的值.所需输出:2,3,5,7,11,13,19实际输出:2,3,5,7
好心提醒.
i=1
x = int(input("Enter the number:"))
for k in range (1, (x+1), 1):
c=0
for j in range (1, (i+1), 1):
a = i%j
if (a==0):
c = c+1
if (c==2):
print (i)
else:
k = k-1
i=i+1
我是Haskell的新手,我正试图以流处理方式实现Euler的Sieve.
当我查看关于素数的Haskell Wiki页面时,我发现了一些神秘的流优化技术.在3.8维基的线性合并中:
primesLME = 2 : ([3,5..] `minus` joinL [[p*p, p*p+2*p..] | p <- primes'])
where
primes' = 3 : ([5,7..] `minus` joinL [[p*p, p*p+2*p..] | p <- primes'])
joinL ((x:xs):t) = x : union xs (joinL t)
它说
" 根据Melissa O'Neill的代码,这里引入了双素数反馈,以防止不必要的记忆,从而防止内存泄漏."
怎么会这样？我无法弄清楚它是如何工作的.
primes haskell sieve-of-eratosthenes lazy-sequences space-leak
count = 0
i = 11
while count <= 1000 and i <= 10000:
if i%2 != 0:
if (i%3 == 0 or i%4 == 0 or i%5 == 0 or i%6 == 0 or i%7 == 0 or i%9 == 0):
continue
else:
print i,'is prime.'
count += 1
i+=1
我试图通过使用循环来生成第1000个素数.我正确地生成素数,但我得到的最后一个素数不是第1000个素数.我如何修改我的代码才能这样做.提前感谢您的帮助.
编辑:我现在知道如何解决这个问题.但有人可以解释为什么以下代码不起作用？这是我在发布第二个之前写的代码.
count = 1
i = 3
while count != 1000:
if i%2 != 0:
for k in range(2,i):
if i%k == 0:
print(i)
count += 1
break …我写了一个函数,使用流无限期地生成质数(维基百科: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 …以下Python代码的Clojure等价物(对于精确算法)是什么？
from itertools import count
from math import sqrt
def prime_gen():
primes = []
for n in count(2):
if all(n%p for p in primes if p <= sqrt(n)):
primes.append(n)
yield n
假设我有一个自然数n,我想要所有素数的列表(或其他)n.
经典的主筛算法在O(n log n)时间和O(n)空间上运行- 它适用于更多命令式语言,但需要从根本上对列表和随机访问进行就地修改.
有一个涉及优先级队列的功能版本,非常漂亮 - 你可以在这里查看.这具有更好的空间复杂度O(n / log(n))(渐近更好但在实际尺度上有争议).不幸的是,时间分析是令人讨厌的,但它几乎O(n^2)(实际上,我认为它是关于O(n log(n) Li(n)),但log(n) Li(n)大约是n).
渐渐地说,使用连续的试验划分,在生成它时检查每个数字的素数实际上会更好,因为这只需要O(1)空间和O(n^{3/2})时间.有没有更好的办法？
编辑:事实证明我的计算完全不正确.文章中的算法是O(n (log n) (log log n))文章解释和证明(并参见下面的答案),而不是我上面提到的复杂的混乱.O(n log log n)如果有一个真正的算法,我仍然喜欢看到一个真正的纯粹算法.
algorithm primes functional-programming sieve-of-eratosthenes
我正在尝试实现一个在其实现中使用自身的另一个实例的流.该流有一些常量元素(使用IntStream.concat),因此只要连接流懒惰地创建非常量部分,这应该有效.我认为使用StreamSupport.intStream重载使用IntStream.concat的供应商("创建一个延迟连接的流")应该足够懒,只能在需要元素时创建第二个分裂器,但是甚至创建流(不评估)它)溢出堆栈.我如何懒洋洋地连接流？
我正试图将这个答案的流媒体素数筛选器移植到Java中.此筛使用其自身的另一个实例(ps = postponed_sieve()在Python代码中).如果我将最初的四个常量元素(yield 2; yield 3; yield 5; yield 7;)分解为它们自己的流,那么很容易将生成器实现为一个分裂器:
/**
* based on https://stackoverflow.com/a/10733621/3614835
*/
static class PrimeSpliterator extends Spliterators.AbstractIntSpliterator {
private static final int CHARACTERISTICS = Spliterator.DISTINCT | Spliterator.IMMUTABLE | Spliterator.NONNULL | Spliterator.ORDERED | Spliterator.SORTED;
private final Map<Integer, Supplier<IntStream>> sieve = new HashMap<>();
private final PrimitiveIterator.OfInt postponedSieve = primes().iterator();
private int p, q, c = 9;
private Supplier<IntStream> s;
PrimeSpliterator() {
super(105097564 /* according to …Eratosthenes的Sieve可以在Haskell中非常巧妙地实现,使用懒惰生成无限列表,然后从尾部删除列表头部的所有倍数:
primes :: [Int]
primes = sieve [2..]
sieve (x:xs) = x : sieve [y | y <- xs, y `mod` x > 0]
我正在尝试学习如何在Java 8中使用流,但我想出是否有一种方法可以在Java中实现与上面的Haskell代码相同的结果.如果我将Haskell惰性列表视为等同于Java流,似乎我需要使用以2为首的流并生成一个删除了所有2的倍数的新流,然后获取该流并生成所有流的新流删除3的倍数,并...
我不知道如何继续.
有没有办法做到这一点,或者当我试图将Java流视为与Haskell列表相当时,我是在欺骗自己？
这是Haskell中定点组合器的通常定义:
fix :: (a -> a) -> a
fix f = let x = f x in x
在https://wiki.haskell.org/Prime_numbers上,他们定义了一个不同的定点组合子:
_Y :: (t -> t) -> t
_Y g = g (_Y g) -- multistage, non-sharing, g (g (g (g ...)))
-- g (let x = g x in x) -- two g stages, sharing
_Y是一个非共享的固定点组合器,在这里安排递归"伸缩"多级素数生产(生产者塔).
这到底是什么意思？在这种情况下,"共享"与"非共享"是什么？有_Y什么不同fix？