在haskell中，如何生成一个所有素数列表，直到数字x？ [英] In haskell how would you go about generating a list of all prime numbers upto a number say x?

问题描述

所以函数会像 primesearch :: Int - > [INT] 。例如， primesearch 4 = [2,3,5,7] 。您是否需要使用筛选功能？或者是否有另一种方法呢？

解决方案

要生成第一个 k 素数或质数< = n ，我推荐一个筛子。哪种筛子取决于你想要的素数。对于小数量的素数，单片Eratosthenes比特筛简单快速。但是如果你想要大量的素数，单片筛将需要太多的记忆，所以分段筛是更好的选择。对于非常小数量的素数（素数 <= 100000 ，比方说），试用分区更容易，但仍然足够快。

如果您想认真使用素数，那么已经有一些hackage包提供了主要生成器，例如 arithmoi 和 NumberSieves 。还有其他的，但据我所知，所有其他人都显着慢。

如果是作业或类似的，哪种方法最合适取决于什么练习应该教。

so the function would be something like primesearch::Int -> [Int]. For example, primesearch 4 = [2,3,5,7]. Would you need to use the sieve function somehow? or is there another way of doing it?

解决方案

To generate the first k prime numbers, or the prime numbers <= n, I recommend a sieve. Which kind of sieve depends on how many primes you want. For small numbers of primes, a monolithic Eratosthenes bit sieve is simple and fast. But if you want large numbers of primes, a monolithic sieve would need too much memory, so a segmented sieve is then the better option. For very small numbers of primes (the primes <= 100000, say), a trial division is even easier, but still sufficiently fast.

If you want to earnestly use primes, there are already packages on hackage which provide prime generators, for example arithmoi and NumberSieves. There are others, but as far as I know, all the others are significantly slower.

If it's for homework or similar, which method is the most appropriate depends on what the exercise shall teach.

这篇关于在haskell中，如何生成一个所有素数列表，直到数字x？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！