Sieve of Eratosthenes: Difference between revisions

← Older edit Newer edit →

Content deleted Content added

Inline

@@ 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.
 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>