Реализации алгоритмов/Решето Эратосфена: различия между версиями
Содержимое удалено Содержимое добавлено
WillNess (обсуждение | вклад) →Haskell: добавил "через массив посегментно"; отредактировал "фильтр" и др. |
|||
Строка 51:
</source>
===Вариация по
<source lang="haskell">
primesToEU n = eulers [2..n] where
Строка 57:
eulers (p:xs) = p : eulers (xs `minus` takeWhile (<= n) (map (p*) (p:xs)))
-- eratos (p:xs) = p : eratos (xs `minus` takeWhile (<= n) (map (p*) [p..] ))
-- -- [p*p, p*p+p..n]▼
</source>
===Поэтапная фильтровка проверками на делимость (не Эратосфен; медленно)===
<source lang="haskell">
primesT = sieve [2..] -- знаменитый код Дейвида Тёрнера
where
sieve (p:xs) = p : sieve [x | x <- xs, rem x p > 0]
</source>
▲С немедленным отсеиванием (медленно):
<source lang="haskell">
primesE = sieve [2..]
Строка 90 ⟶ 85 :
<source lang="haskell">
primesB = 2 : minus [3..] (foldr (\p r-> (p*p) : union [p*p+p,p*p+2*p..] r)
[] primesB)
union (x:xs) (y:ys) = case (compare x y) of
Строка 96 ⟶ 91 :
EQ -> x : union xs ys
GT -> y : union (x:xs) ys
</source>
===Просеивание через массив, посегментно между квадратами простых чисел===
<source lang="haskell">
import Data.Array.Unboxed
ps = 2 : [n | (r:q:_, px) <- (zip . tails . (2:) . map (^2) <*> inits) ps,
(n,True) <- assocs (
accumArray (\_ _ -> False) True (r+1,q-1)
[(m,()) | p <- px, let s=r`div`p*p, m <- [s+p,s+2*p..q-1]]
</source>
| |||