<commit_before>{- |
module: GenuineSieve
description: A simple implementation of the genuine sieve of Eratosphenes
license: MIT

maintainer: <NAME> <<EMAIL>>
stability: provisional
portability: portable
-}
module GenuineSieve
  ( primes )
where

import qualified Heap
import qualified Data.List as List
import OpenTheory.Primitive.Natural

newtype Sieve =
    Sieve { unSieve :: (Natural, Heap.Heap (Natural,Natural)) }

instance Show Sieve where
  show s = show (unSieve s)

perimeter :: Sieve -> Natural
perimeter s = fst (unSieve s)

initial :: Sieve
initial =
    Sieve (1, Heap.empty lep)
  where
    lep (p1,_) (p2,_) = p1 <= p2

next :: Sieve -> (Natural,Sieve)
next s =
    let (b, s') = increment s in
    if b then (perimeter s', s') else next s'

increment :: Sieve -> (Bool,Sieve)
increment =
    \s ->
      let (n,ps) = unSieve s in
      let n' = n + 2 in
      let (m,ps') = bump ps in
      if m <= n'
        then (False, Sieve (m,ps'))
        else (True, Sieve (n', Heap.add (n' * n', 2 * n') ps))
  where
    bump ps =
      case Heap.remove ps of
        Nothing -> (5,ps)
        Just ((kp,p),ps') -> (kp, Heap.add (kp + p, p) ps')

primes :: [Natural]
primes = 2 : List.unfoldr (Just . next) initial<commit_msg>Reference implementation of the genuine sieve<commit_after>{- |
module: GenuineSieve
description: A simple implementation of the genuine sieve of Eratosphenes
license: MIT

maintainer: <NAME> <<EMAIL>>
stability: provisional
portability: portable
-}
module GenuineSieve
  ( primes )
where

import qualified Heap
import qualified Data.List as List
import OpenTheory.Primitive.Natural

newtype Sieve =
    Sieve { unSieve :: (Natural, Heap.Heap (Natural,Natural)) }

instance Show Sieve where
  show s = show (unSieve s)

perimeter :: Sieve -> Natural
perimeter (Sieve (n,_)) = n

initial :: Sieve
initial =
    Sieve (9, Heap.empty lep)
  where
    lep (p1,_) (p2,_) = p1 <= p2

add :: Natural -> Sieve -> Sieve
add p (Sieve (n,ps)) = Sieve (n, Heap.add (p * p, 2 * p) ps)

bump :: Sieve -> Sieve
bump (Sieve (_,ps)) =
    case Heap.remove ps of
      Nothing -> error "GenuineSieve.bump"
      Just ((kp,p),ps') -> Sieve (kp, Heap.add (kp + p, p) ps')

advance :: Natural -> Sieve -> [Natural]
advance m s =
    let n = perimeter s in
    if m < n
      then m : advance (m + 2) (add m s)
      else advance (if m == n then m + 2 else m) (bump s)

primes :: [Natural]
primes = 2 : advance 3 initial
{'fraction_non_alphanumeric': 0.1302918207973695, 'fraction_numerical': 0.007809288943690916, 'mean_word_length': 3.0566666666666666, 'pattern_counts': {'":': 0, '<': 13, '<?xml version=': 0, '>': 23, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1357367', 'n_tokens_mistral': 920, 'n_tokens_neox': 877, 'n_words': 311}