Step by Step solution about How to resolve the algorithm Sequence of primes by trial division step by step in the Haskell programming language

List Comprehension with Filters:

[n | n <- [2..], []==[i | i <- [2..n-1], rem n i == 0]]

This list comprehension generates a list of prime numbers. It iterates over numbers from 2 to infinity and filters for numbers that are only divisible by 1 and themselves.

Nested List Comprehension:

[n | n <- [2..], []==[i | i <- [2..n-1], j <- [i,i+i..n], j==n]]

This list comprehension also generates primes, but it has a nested filter. The outer loop iterates over numbers from 2 to infinity, and the inner loop iterates over all multiples of each number. If any of these multiples equal the original number, it's not prime.

Foldr with Filter:

foldr (\x r -> x : filter ((> 0).(`rem` x)) r) [] [2..]

This code uses foldr to generate a list of primes. It starts with an empty list, then iterates over the numbers from 2 to infinity, filtering out non-prime numbers as it goes.

unfoldr with Filter:

Data.List.unfoldr (\(x:xs) -> Just (x, filter ((> 0).(`rem` x)) xs)) [2..]

This code uses unfoldr to generate a list of primes. Similar to the previous example, it iterates over the numbers from 2 to infinity and filters out non-prime numbers.

primesFromTo Function:

primesFromTo n m = filter isPrime [n..m]

This function generates a list of prime numbers within a given range [n, m]. It uses the isPrime function to check if a number is prime.

primes Function (Recursive):

primes = 2 : [n | n <- [3..], foldr (\p r-> p*p > n || rem n p > 0 && r)
                                   True primes]

This function generates a list of prime numbers recursively. It starts with the list [2, 3], then iterates over numbers from 5 to infinity. For each number, it checks if it's divisible by any of the previously generated primes, and if not, it's added to the list.

primes Function (Tail Recursive):

primes = 2 : 3 : [n | n <- [5,7..], foldr (\p r-> p*p > n || rem n p > 0 && r)
                                         True (drop 1 primes)]

This function is a tail-recursive version of the previous one, which is more efficient.

primes Function (Scanl):

primes = 2 : 3 : [n | n <- scanl (+) 7 (cycle [4,2]),
                                    foldr (\p r-> p*p > n || rem n p > 0 && r)
                                          True (drop 2 primes)]

This function generates primes using a scanning function and a cycle. It's an alternative approach to the previous one.

wheelGen Function:

wheelGen :: Int -> ([Int],Int,[Int])
wheelGen n = loop 1 3 [2] [2] where
 loop i frst wps gps =
   if i >= n then (wps, frst, gps) else
     ...

This function generates a list of prime numbers using a "wheel primality test," which is a sieve-based algorithm that's faster than the standard sieve of Eratosthenes for larger numbers.

primesTDW Function:

primesTDW :: () -> [Int]
primesTDW() = wheelPrimes ++ _Y (
               (firstSievePrime :) . sieve (firstSievePrime + head gaps)
                                           (tail $ cycle gaps)) where
 ...

This function generates primes using a "time-delay wheel primality test," which is a variation of the wheel primality test that's more efficient.

primesT Function:

primesT = sieve [2..]
         where
         sieve (p:xs) = p : sieve [x | x <- xs, rem x p /= 0]

This function generates primes using the Sieve of Eratosthenes, which is a standard algorithm for finding primes.

primesTo Function:

primesTo m = sieve [2..m]
  where
  sieve (p:xs) | p*p > m   = p : xs
               | otherwise = p : sieve [x | x <- xs, rem x p /= 0]

This function generates primes up to a given bound m using the Sieve of Eratosthenes.

primesPT Function:

primesPT = sieve primesPT [2..]
          where
          sieve ~(p:ps) (x:xs) = x : after (p*p) xs
                                       (sieve ps . filter ((> 0).(`rem` p)))
          after q (x:xs) | x < q = x : after q xs f
                           | otherwise = f (x:xs)

This function generates primes using a "primes that divide the previous term" (PT) sieve, which is a variant of the Sieve of Eratosthenes that's faster for larger numbers.

primesPTDW Function:

primesPTDW :: () -> [Int] -- nested filters, no matter how much postponed,
primesPTDW() = -- causes mucho allocation of deferred thunks!
   wheelPrimes ++ _Y ((firstSievePrime :) . sieve cndts) where
 ...

This function generates primes using a "time-delay primes that divide the previous term" (PT) sieve, which is a variation of the PT sieve that's more efficient.

primesST Function:

primesST = 2 : 3 : sieve 5 9 (drop 2 primesST) (inits $ tail primesST)
  where
  sieve x q ps (fs:ft) = filter (\y-> all ((/=0).rem y) fs) [x,x+2..q-2]
                         ++ sieve (q+2) (head ps^2) (tail ps) ft

This function generates primes using a "self-testing sieve," which is a sieve algorithm that doesn't store any prime numbers but instead uses a list of factors to eliminate non-primes.

[n | n <- [2..], []==[i | i <- [2..n-1], rem n i == 0]]


[n | n <- [2..], []==[i | i <- [2..n-1], j <- [i,i+i..n], j==n]]


foldr (\x r -> x : filter ((> 0).(`rem` x)) r) [] [2..]


Data.List.unfoldr (\(x:xs) -> Just (x, filter ((> 0).(`rem` x)) xs)) [2..]


primesFromTo n m = filter isPrime [n..m]


-- primes = filter isPrime [2..]
primes = 2 : [n | n <- [3..], foldr (\p r-> p*p > n || rem n p > 0 && r)
                                    True primes]


primes = 2 : 3 : [n | n <- [5,7..], foldr (\p r-> p*p > n || rem n p > 0 && r)
                                          True (drop 1 primes)]
       = [2,3,5] ++ [n | n <- scanl (+) 7 (cycle [4,2]),
                                     foldr (\p r-> p*p > n || rem n p > 0 && r)
                                           True (drop 2 primes)]
    -- = [2,3,5,7] ++ [n | n <- scanl (+) 11 (cycle [2,4,2,4,6,2,6,4]), ... (drop 3 primes)]


-- autogenerates wheel primes, first sieve prime, and gaps
wheelGen :: Int -> ([Int],Int,[Int])
wheelGen n = loop 1 3 [2] [2] where
  loop i frst wps gps =
    if i >= n then (wps, frst, gps) else
    let nfrst = frst + head gps
        nhts = (length gps) * (frst - 1)
        cmpsts = scanl (\ c g -> c + frst * g)  (frst * frst) (cycle gps)
        cull n (g:gs') cs@(c:cs') og
            | nn >= c = cull nn gs' cs' (og + g) -- n == c; never greater!
            | otherwise = (og + g) : cull nn gs' cs 0 where nn = n + g
    in nfrst `seq` nhts `seq` loop (i + 1) nfrst (wps ++ [frst]) $ take nhts
                                     $ cull nfrst (tail $ cycle gps) cmpsts 0

(wheelPrimes, firstSievePrime, gaps) = wheelGen 7

primesTDW :: () -> [Int]
primesTDW() = wheelPrimes ++ _Y (
                (firstSievePrime :) . sieve (firstSievePrime + head gaps)
                                            (tail $ cycle gaps)) where
  _Y g = g (_Y g)        -- non-sharing multi-stage fixpoint combinator
  sieve cnd gps bps = xtrprms cnd gps where
    xtrprms n (g:gs') -- strictly filtered by base primes <= sqrt - faster!
      | any ((==) 0 . rem n)
            (takeWhile ((<= n) . flip (^) 2) bps) = xtrprms (n + g) gs'
      | otherwise = n : xtrprms (n + g) gs'


primesT = sieve [2..] 
          where
          sieve (p:xs) = p : sieve [x | x <- xs, rem x p /= 0]
-- map head 
--  . iterate (\(p:xs) -> filter ((> 0).(`rem` p)) xs) $ [2..]


primesTo m = sieve [2..m] 
   where
   sieve (p:xs) | p*p > m   = p : xs
                | otherwise = p : sieve [x | x <- xs, rem x p /= 0]
-- (\(a,b:_) -> map head a ++ b) . span ((< m).(^2).head) 
--   $ iterate (\(p:xs) -> filter ((>0).(`rem`p)) xs) [2..m]


primesPT = sieve primesPT [2..]
           where
           sieve ~(p:ps) (x:xs) = x : after (p*p) xs 
                                        (sieve ps . filter ((> 0).(`rem` p)))
           after q (x:xs) f | x < q = x : after q xs f 
                            | otherwise = f (x:xs)
-- fix $ concatMap (fst.fst) . iterate (\((_,t),p:ps) -> 
--         (span (< head ps^2) [x | x <- t, rem x p > 0], ps)) . (,) ([2,3],[4..])


primesPTDW :: () -> [Int] -- nested filters, no matter how much postponed,
primesPTDW() = -- causes mucho allocation of deferred thunks!
    wheelPrimes ++ _Y ((firstSievePrime :) . sieve cndts) where
  _Y g = g (_Y g)        -- non-sharing multi-stage fixpoint combinator
  cndts = scanl (+) (firstSievePrime + head gaps) (tail $ cycle gaps)
  sieve xs (bp:bps') = after xs where
    q = bp * bp
    after (x:xs') | x >= q = sieve (filter ((> 0) . (`rem` bp)) xs') bps'
                  | otherwise = x : after xs'


import Data.List (inits)

primesST = 2 : 3 : sieve 5 9 (drop 2 primesST) (inits $ tail primesST) 
   where
   sieve x q ps (fs:ft) = filter (\y-> all ((/=0).rem y) fs) [x,x+2..q-2]
                          ++ sieve (q+2) (head ps^2) (tail ps) ft