The sieve of Sundaram: Difference between revisions
Content added Content deleted
(→{{header|Haskell}}: Added a draft version in Haskell) |
|||
Line 280: | Line 280: | ||
As a check, the 1,000,000 Sundaram prime would again have been 15,485,867 |
As a check, the 1,000,000 Sundaram prime would again have been 15,485,867 |
||
</pre> |
</pre> |
||
=={{header|Haskell}}== |
|||
<lang haskell>import Data.List (intercalate, transpose) |
|||
import Data.List.Split (chunksOf) |
|||
import qualified Data.Set as S |
|||
import Text.Printf (printf) |
|||
--------------------- SUNDARAM PRIMES -------------------- |
|||
sundaram :: Integral a => a -> [a] |
|||
sundaram n = |
|||
[ succ (2 * x) |
|||
| x <- [1 .. m], |
|||
x `S.notMember` excluded |
|||
] |
|||
where |
|||
m = div (pred n) 2 |
|||
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 :: |
|||
(Integral a1, RealFrac a2, Floating a2) => a2 -> [a1] |
|||
nSundaramPrimes n = |
|||
sundaram $ floor $ (2.4 * n * log n) / 2 |
|||
--------------------------- TEST ------------------------- |
|||
main :: IO () |
|||
main = do |
|||
putStrLn "First 100 Sundaram primes (starting at 3):\n" |
|||
(putStrLn . table " " . chunksOf 10) $ |
|||
show <$> nSundaramPrimes 100 |
|||
table :: String -> [[String]] -> String |
|||
table gap rows = |
|||
let ws = maximum . fmap length <$> transpose rows |
|||
pw = printf . flip intercalate ["%", "s"] . show |
|||
in unlines $ intercalate gap . zipWith pw ws <$> rows</lang> |
|||
{{Out}} |
|||
<pre>First 100 Sundaram primes (starting at 3): |
|||
3 5 7 11 13 17 19 23 29 31 |
|||
37 41 43 47 53 59 61 67 71 73 |
|||
79 83 89 97 101 103 107 109 113 127 |
|||
131 137 139 149 151 157 163 167 173 179 |
|||
181 191 193 197 199 211 223 227 229 233 |
|||
239 241 251 257 263 269 271 277 281 283 |
|||
293 307 311 313 317 331 337 347 349 353 |
|||
359 367 373 379 383 389 397 401 409 419 |
|||
421 431 433 439 443 449 457 461 463 467 |
|||
479 487 491 499 503 509 521 523 541 547</pre> |
|||
=={{header|Julia}}== |
=={{header|Julia}}== |