В haskell как бы вы сгенерировали список всех простых чисел до числа, скажем, x?

Question

, поэтому функция будет выглядеть примерно так: primesearch::Int -> [Int]. Например, primesearch 4 = [2,3,5,7]. Нужно ли вам как-то использовать функцию сита? или есть другой способ сделать это?

Answer 1

Для генерации первых k простых чисел или простых чисел <= n я рекомендую сито. Какое сито зависит от того, сколько простых чисел вы хотите. Для небольшого числа простых чисел монолитное сито Эратосфена простое и быстрое. Но если вам нужно большое количество простых чисел, монолитное сито потребует слишком много памяти, поэтому сегментированное сито является лучшим вариантом. Для очень небольшого числа простых чисел (скажем, простых чисел <= 100000) пробное деление еще проще, но все же достаточно быстро.

Если вы хотите искренне использовать простые числа, на hackage уже есть пакеты с простыми генераторами, например arithmoi и NumberSieves . Есть и другие, но, насколько я знаю, все остальные значительно медленнее.

Если это домашняя работа или аналогичная, то какой метод является наиболее подходящим, зависит от того, чему научит упражнение.

Answer 2

Я учусь и играю с Haskell, в частности изучаю List Compceptionsion, поэтому я попытался выпустить тот, который представляет «все» простые числа.

Я вышел с этим:

[x | x <- 2:[3,5..], and( map (\y -> 0 /= x `mod` y) (take (x`quot`4-1) [3,5..]))]

И первые N простых чисел могут быть получены с помощью функции take:

take N [x | x <- 2:[3,5..], and( map (\y -> 0 /= x `mod` y) (take (x`quot`4-1) [3,5..]))]

, которая работает без бесконечных циклов благодаря ленивой оценке бесконечных диапазонов.

Значение: Это понимание списка всех «нечетных чисел плюс число 2»

[x | x <- 2:[3,5..], ... ]

с условием, что для каждого числа в списке «всегда должно быть верно»...

and( ... )

... что "это не 0 остаток" числа, примененного ко всем ...

map (\y -> 0 /= x `mod` y)

... "первая половина", котораяменьше числа кандидата ...

take (x`quot`4-1)

... из набора "всех нечетных чисел".

 [3,5..]

Я слишком новичок в Haskell, чтобы оценить эффективностьдля реального применения (вероятно, хорошо только для небольших чисел), но я нахожу классным, что в Haskell можновыразить список простых чисел таким образом

Answer 3

Еще одна забавная статья - http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf. На нее ссылается ссылка qrl, но ее стоит проверить самостоятельно.Он предоставляет более подробные объяснения, чем ссылка qrl, но не обеспечивает почти столько реализаций.

Answer 4

Вот самый быстрый из самых простых, в низких диапазонах до миллиона простых чисел или около того:

{-# OPTIONS_GHC -O2 #-}
import Data.Array.Unboxed

primesToA m = sieve 3 (array (3,m) [(i,odd i) | i<-[3..m]]
                       :: UArray Int Bool)
  where
    sieve p a 
      | p*p > m   = 2 : [i | (i,True) <- assocs a]
      | a!p       = sieve (p+2) $ a//[(i,False) | i <- [p*p, p*p+2*p..m]]
      | otherwise = sieve (p+2) a

(спасибо Дэниелу Фишеру за добавление этой маленькой вещи, называемой явной сигнатурой типа, что позволяет работать с неупакованными массивами). Кикер, здесь за кулисами происходит деструктивное обновление. (очевидно, нет) .

Что касается статьи JFP , в ней отсутствует ключевая причина для ужасной неэффективности кода Тернера - на самом деле она игнорируется как неактуальная - и предлагает довольно запутанные размышления о сите , а также его звуковой и поучительный математический анализ.

edit: это было в ответ на ваш заголовок, но в тексте кажется, что вы хотите сгенерировать заданное количество простых чисел, а не простых чисел до заданного значения. Значение верхнего предела легко переоценить , так что

nPrimes n | n > 3 =
  let 
    x = fromIntegral n
    m = ceiling $ x*(log x + log (log x))
  in
    take n $ primesToA m