Sieve of Eratosthenes: Difference between revisions
Content deleted Content added
Langurmonkey (talk | contribs) |
imported>Polarit new elm version |
||
Line 6,646: | Line 6,646: | ||
<pre>The primes up to 100 are: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97. |
<pre>The primes up to 100 are: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97. |
||
Found 78498 primes to 1000000 in 192 milliseconds.</pre> |
Found 78498 primes to 1000000 in 192 milliseconds.</pre> |
||
=={{header|Elm with immutable arrays}}== |
|||
<syntaxhighlight lang="elm"> |
|||
module PrimeArray exposing (main) |
|||
import Array exposing (Array, foldr, map, set) |
|||
import Html exposing (div, h1, p, text) |
|||
import Html.Attributes exposing (style) |
|||
{- |
|||
The Eratosthenes sieve task in Rosetta Code does not allow |
|||
the use of modulo function (modBy or remainderBy). |
|||
Thus the work list is converted into an indexed work array |
|||
as Elm has no indexes for lists. |
|||
In this method we need no division remainder calculations, |
|||
as we just set the markings of non-primes into the array. |
|||
We need the indexes that we know, where the marking of the non-primes |
|||
shall be set. |
|||
Live: https://ellie-app.com/pTHJyqXcHtpa1 |
|||
-} |
|||
alist = |
|||
List.range 2 150 |
|||
-- Work array contains integers 2 ... 149 |
|||
workArray = |
|||
Array.fromList alist |
|||
n : Int |
|||
n = |
|||
List.length alist |
|||
-- The max index of integers used in search for primes |
|||
-- limit * limit < n |
|||
-- equal: limit <= √n |
|||
limit : Int |
|||
limit = |
|||
round (0.5 + sqrt (toFloat n)) |
|||
-- Remove zero cells of the array |
|||
findZero : Int -> Bool |
|||
findZero = |
|||
\el -> el > 0 |
|||
zeroFree : Array Int |
|||
zeroFree = |
|||
Array.filter findZero workResult |
|||
nrFoundPrimes = |
|||
Array.length zeroFree |
|||
workResult : Array Int |
|||
workResult = |
|||
loopI 2 limit workArray |
|||
-- As Elm has no loops (for, while, until) |
|||
-- we must use recursion instead! |
|||
-- The outer loop of prime search with increasing variable i |
|||
-- The search of prime starts allways saving (not setting zero) |
|||
-- the first location of the found prime as the later found values are |
|||
-- multiples and set zero |
|||
-- The recursive loop of variable i follows: |
|||
loopI : Int -> Int -> Array Int -> Array Int |
|||
loopI i imax arr = |
|||
if i > imax then |
|||
arr |
|||
else |
|||
let |
|||
arr2 = |
|||
phase i arr |
|||
in |
|||
loopI (i + 1) imax arr2 |
|||
-- The helper function |
|||
phase : Int -> Array Int -> Array Int |
|||
phase i = |
|||
arrayMarker i (2 * i - 2) n |
|||
lastPrime = |
|||
Maybe.withDefault 0 <| Array.get (nrFoundPrimes - 1) zeroFree |
|||
outputArrayInt : Array Int -> String |
|||
outputArrayInt arr = |
|||
decorateString <| |
|||
foldr (++) "" <| |
|||
Array.map (\x -> String.fromInt x ++ " ") arr |
|||
decorateString : String -> String |
|||
decorateString str = |
|||
"[ " ++ str ++ "]" |
|||
-- Recursively marking the multiples of p with zero |
|||
-- This loop operates with constant p |
|||
arrayMarker : Int -> Int -> Int -> Array Int -> Array Int |
|||
arrayMarker p min max arr = |
|||
let |
|||
arr2 = |
|||
set min 0 arr |
|||
min2 = |
|||
min + p |
|||
in |
|||
if min < max then |
|||
arrayMarker p min2 max arr2 |
|||
else |
|||
arr |
|||
main = |
|||
div [ style "margin" "2%" ] |
|||
[ h1 [] [ text "Sieve of Eratosthenes" ] |
|||
, text ("List of integers [2, ... ," ++ String.fromInt n ++ "]") |
|||
, p [] [ text ("Total integers " ++ String.fromInt n) ] |
|||
, p [] [ text ("Max prime of search " ++ String.fromInt limit) ] |
|||
, p [] [ text ("The largest found prime " ++ String.fromInt lastPrime) ] |
|||
, p [ style "color" "blue", style "font-size" "1.5em" ] |
|||
[ text (outputArrayInt zeroFree) ] |
|||
, p [] [ text ("Found " ++ String.fromInt nrFoundPrimes ++ " primes") ] |
|||
] |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
List of integers [2, ... ,149] |
|||
Total integers 149 |
|||
Max prime of search 13 |
|||
The largest found prime 149 |
|||
[ 2 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 ] |
|||
Found 35 primes |
|||
</pre> |
|||