相关疑难解决方法(0)

这不是作业,我只是好奇.

INFINITE是这里的关键词.

我希望在primes()中使用它作为p.我相信这是Haskell中的内置函数.

所以,答案不能像"Just do a Sieve"那样天真.

首先,您不知道将消耗多少连续素数.好吧,假设你可以一次编制100个.您是否会使用相同的Sieve方法以及素数公式的频率？

我更喜欢非并发方法.

感谢您阅读(和写作;))!

Java 8引入了一个类似Scala的Stream的Stream类,这是一个功能强大的惰性结构,使用它可以非常简洁地执行这样的操作:

def from(n: Int): Stream[Int] = n #:: from(n+1)

def sieve(s: Stream[Int]): Stream[Int] = {
  s.head #:: sieve(s.tail filter (_ % s.head != 0))
}

val primes = sieve(from(2))

primes takeWhile(_ < 1000) print  // prints all primes less than 1000

我想知道是否有可能在Java 8中这样做,所以我写了这样的东西:

IntStream from(int n) {
    return IntStream.iterate(n, m -> m + 1);
}

IntStream sieve(IntStream s) {
    int head = s.findFirst().getAsInt();
    return IntStream.concat(IntStream.of(head), sieve(s.skip(1).filter(n -> n % head != 0)));
}

IntStream primes …

我无法理解这段代码:

let
  sieve (p:xs) = p : sieve (filter (\ x -> x `mod` p /= 0) xs)
in sieve [2 .. ]

有人可以为我分手吗？我知道它有递归,但这就是问题我无法理解这个例子中的递归是如何工作的.

我是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的代码,这里引入了双素数反馈,以防止不必要的记忆,从而防止内存泄漏."

怎么会这样？我无法弄清楚它是如何工作的.

假设我有一个自然数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)如果有一个真正的算法,我仍然喜欢看到一个真正的纯粹算法.