The sieve of Sundaram: Difference between revisions
Content added Content deleted
(→{{header|Haskell}}: Dropped use of Data.Set) |
|||
| Line 284: | Line 284: | ||
<lang haskell>import Data.List (intercalate, transpose) |
<lang haskell>import Data.List (intercalate, transpose) |
||
import Data.List.Split (chunksOf) |
import Data.List.Split (chunksOf) |
||
import qualified Data.Set as S |
|||
import Text.Printf (printf) |
import Text.Printf (printf) |
||
| Line 289: | Line 290: | ||
sundaram :: Integral a => a -> [a] |
sundaram :: Integral a => a -> [a] |
||
sundaram n = |
sundaram n = |
||
[ succ (2 * x) |
|||
| x <- [1 .. m], |
|||
x `S.notMember` excluded |
|||
| ⚫ | |||
where |
where |
||
m = div (pred n) 2 |
m = div (pred n) 2 |
||
excluded = |
excluded = |
||
S.fromList |
|||
[ 2 * i * j + i + j |
|||
| let fm = fromIntegral m, |
|||
i <- [1 .. floor (sqrt (fm / 2))], |
|||
let fi = fromIntegral i, |
|||
j <- [i .. floor ((fm - fi) / succ (2 * fi))] |
|||
| ⚫ | |||
] |
|||
nSundaramPrimes :: |
nSundaramPrimes :: |
||
| Line 304: | Line 310: | ||
nSundaramPrimes n = |
nSundaramPrimes n = |
||
sundaram $ floor $ (2.4 * n * log n) / 2 |
sundaram $ floor $ (2.4 * n * log n) / 2 |
||
| Line 312: | Line 319: | ||
(putStrLn . table " " . chunksOf 10) $ |
(putStrLn . table " " . chunksOf 10) $ |
||
show <$> nSundaramPrimes 100 |
show <$> nSundaramPrimes 100 |
||
------------------------- GENERIC ------------------------ |
|||
gaps _ [] = [] |
|||
gaps (x : xs) yys@(y : ys) |
|||
| x >= y = gaps xs ys |
|||
| otherwise = x : gaps xs yys |
|||
table :: String -> [[String]] -> String |
table :: String -> [[String]] -> String |
||