-
Notifications
You must be signed in to change notification settings - Fork 4
/
primes.hs
119 lines (84 loc) · 2.41 KB
/
primes.hs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
-- Primality testing using two methods
main :: IO ()
main = do
arg1 <- read_arg1
let n = fromString arg1
print $ "Finding prime no. " ++ toString n
let a = primeA n
b = primeB n
print $ "Sieve of Eratosthenes: " ++ toString a
print $ "Divisor testing: " ++ toString b
Ret ()
-- Method 1: sieve of Eratosthenes
primesA :: [Integer]
primesA =
let sieve l =
case l of
[] -> [] -- should not happen
h:t -> h : filter (\n -> not $ n `mod` h == 0) (sieve t)
in sieve $ numbers 2
primeA :: Integer -> Integer
primeA n = idx n primesA
-- Method 2: divisor testing
isPrime :: Integer -> Bool
isPrime n =
let checkPrime div n = if n < div * div then True
else if n `mod` div == 0 then False
else checkPrime (div + 1) n
in if n < 2 then False else checkPrime 2 n
primesB :: [Integer]
primesB = filter isPrime $ numbers 2
primeB :: Integer -> Integer
primeB n = idx n primesB
-- Helper functions
f $ x = f x
not :: Bool -> Bool
not b = case b of True -> False
False -> True
filter :: (a -> Bool) -> [a] -> [a]
filter f l =
case l of
[] -> []
h:t -> if f h then h : filter f t
else filter f t
idx :: Integer -> [Integer] -> Integer
idx n l =
case l of
[] -> ~1 -- should not happen
h:t -> if n == 0 then h else idx (n - 1) t
numbers :: Integer -> [Integer]
numbers n = n : numbers (n + 1)
-- I/O helpers
reverse :: [a] -> [a]
reverse l =
let revA a l = case l of [] -> a
h:t -> revA (h:a) t
in revA [] l
fromString :: String -> Integer
fromString s =
let fromStringI i limit acc s =
if limit == i then acc
else if limit < i then acc
else
fromStringI (i + 1) limit (acc * 10 + (str_elem s i - 48)) s
in fromStringI 0 (strlen s) 0 s
toString :: Integer -> String
toString i =
let toString0 i =
if i == 0 then []
else (i `mod` 10 + 48) : toString0 (i `div` 10)
in if i < 0 then "-" ++ (implode $ reverse $ toString0 (0-i))
else if i == 0 then "0"
else implode $ reverse $ toString0 i
implode l =
case l of
[] -> ""
h:t -> #(__Implode) h ++ implode t
read_arg1 = Act (#(cline_arg) " ")
print s = Act (#(stdout) (s ++ "\n"))
-- Overloads
s1 ++ s2 = #(__Concat) s1 s2
str_elem :: String -> Integer -> Integer
str_elem s i = #(__Elem) s i
strlen :: String -> Integer
strlen s = #(__Len) s