Haskell Pratice - Prime
今日目標算是達成了，明天再繼續。原始想法很簡單，如何寫出一個 prime list ? 於是我就寫了第一版
prime :: Integer -> Bool
prime x
| x == 2 = True
| otherwise =
isPrime [2..sq] x
where sq = truncate (sqrt (fromIntegral x)) + 1
isPrime :: [Integer] -> Integer -> Bool
isPrime x y =
case x of
[] -> False
x:xs -> (y `mod` x == 0) || isPrime xs
makePrimeList :: [Integer] -> [Integer]
makePrimeList x =
case x of
[] -> []
x:xs -> if prime x then
[x] ++ makePrimeList xs
else
makePrimeList xs其中的 where sq = truncate (sqrt (fromIntegral x)) + 1 是在 Josh Ko 的幫助下寫出來的，但是我得隔日再戰，我很明確的知道是轉型問題，但是並不是能夠完全說清楚為什麼要這樣做(他有說明，但是我得再看一下書)。
而且在這一版中的 isPrime 實在是太暴力了，其實可以用 map + and (or fold) 寫出來，並不一定要用 recursive 寫，所以我採用了另外一個寫法，即是檢查到 `mod` == 0 就停下來。
isPrime_2 :: Integer -> [Integer] -> Bool
isPrime_2 x y
| x == 2 = True
| otherwise =
case y of
[] -> True
y:ys -> if y < sq then
if (x `mod` y == 0) then False
else isPrime_2 x ys
else True
where sq = truncate (sqrt (fromIntegral x)) + 1速度是明顯快上不少，但這版對我而言只剩最後一個問題，就是每呼叫一次 sq 就要算一次，我目前唯一想到的解法是，把 sq 也當成引數，於是我就寫成
isPrime_3 :: Integer -> [Integer] -> Bool
isPrime_3 x y
| x == 2 = True
| otherwise =
isPrime_3' x y (truncate (sqrt (fromIntegral x)) + 1)
isPrime_3' :: Integer -> [Integer] -> Integer -> Bool
isPrime_3' x y sq =
case y of
[] -> True
y:ys -> if y < sq then
if (x `mod` y == 0) then False
else isPrime_3' x ys sq
else True最後，再寫一個 makePrimeList 的 code 就搞定了
makePrimeList :: Integer -> [Integer]
makePrimeList x = makePrimeList_2 [2..x] []
makePrimeList_2 :: [Integer] -> [Integer] -> [Integer]
makePrimeList_2 u v =
case u of
[] -> []
x:xs -> if isPrime_3 x v then
[x] ++ makePrimeList_2 xs (v++[x])
else
makePrimeList_2 xs v最後 run 一下成果
*Main> makePrimeList 100
[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]其實還可以更快，但是就明天再來來，依現在的程度寫出的 code ，雖然普通，可是很開心。
---
本週目標：練習 Prime
馬上就打了自己的嘴吧，我試著嘗試產生 6n+1 6n+5 的 list 用以減少 prime 的檢查次數，於是很粗糙的寫了如下的 code
makeList :: Integer -> Integer -> Bool -> [Integer] -> [Integer]
makeList e c b x =
if c < e then
if b then
makeList e (c+4) False (x ++ [c])
else
makeList e (c+2) True (x ++ [c])
else
x然後將 makePrimeList 改成如下
makePrimeList :: Integer -> [Integer]
makePrimeList x = makePrimeList_2 ([2, 3] ++ makeList x 5 False []) []結果速度反而慢到嚇人啊...Orz 完全不知道為什麼，看來要好好研究了 XD。
