First of all, mod
is slow so use rem
in situations where it doesn't matter (when you aren't dealing with negatives, basically). Secondly, use Criterion to show (to yourself) what is faster and what changes are actually optimizations. I know I'm not giving a full answer to you question with this, but its a good place for you (and other potential answerers) to start, so here's some code:
import List
import Criterion.Main
main = do
str <- getLine
let run f = length . f
input = read str :: Integer
defaultMain [ bench "primes" (nf (run primes) input)
, bench "primes'" (nf (run primes') input)
, bench "primes''" (nf (run primes'') input)
, bench "primesTMD" (nf (run primesTMD) input)
, bench "primes'TMD" (nf (run primes'TMD) input)
, bench "primes''TMD" (nf (run primes''TMD) input)
]
putStrLn . show . length . primes'' $ (read str :: Integer)
-- primeira implementação
primes n
| n < 2 = []
| n == 2 = [2]
| n `mod` 2 == 0 = primes'
| otherwise = if (find (\x -> n `mod` x == 0) primes') == Nothing then
n:primes'
else
primes'
where primes' = primes (n - 1)
primesTMD n
| n < 2 = []
| n == 2 = [2]
| n `mod` 2 == 0 = primes'
| otherwise = if (find (\x -> n `rem` x == 0) primes') == Nothing then
n:primes'
else
primes'
where primes' = primesTMD (n - 1)
-- segunda implementação
primes' :: Integer -> [Integer]
primes' n = sieve $ 2 : [3,5..n]
where sieve :: [Integer] -> [Integer]
sieve [] = []
sieve l@(x:xs)
| x*x >= n = l
| otherwise = x : sieve list'
where list' = filter (\y -> y `mod` x /= 0) xs
primes'TMD :: Integer -> [Integer]
primes'TMD n = sieve $ 2 : [3,5..n]
where sieve :: [Integer] -> [Integer]
sieve [] = []
sieve l@(x:xs)
| x*x >= n = l
| otherwise = x : sieve list'
where list' = filter (\y -> y `rem` x /= 0) xs
-- terceira implementação
primes'' :: Integer -> [Integer]
primes'' n = 2 : sieve 3 [3,5..n]
where sieve :: Integer -> [Integer] -> [Integer]
sieve _ [] = []
sieve m l@(x:xs)
| m*m >= n = l
| x < m*m = x : sieve m xs
| otherwise = sieve (m + 2) list'
where list'= filter (\y -> y `mod` m /= 0) l
primes''TMD :: Integer -> [Integer]
primes''TMD n = 2 : sieve 3 [3,5..n]
where sieve :: Integer -> [Integer] -> [Integer]
sieve _ [] = []
sieve m l@(x:xs)
| m*m >= n = l
| x < m*m = x : sieve m xs
| otherwise = sieve (m + 2) list'
where list'= filter (\y -> y `rem` m /= 0) l
Notice the improved runtime of the variants using rem
:
$ ghc --make -O2 sieve.hs
$./sieve
5000
...
benchmarking primes
mean: 23.88546 ms, lb 23.84035 ms, ub 23.95000 ms
benchmarking primes'
mean: 775.9981 us, lb 775.4639 us, ub 776.7081 us
benchmarking primes''
mean: 837.7901 us, lb 836.7824 us, ub 839.0260 us
benchmarking primesTMD
mean: 16.15421 ms, lb 16.11955 ms, ub 16.19202 ms
benchmarking primes'TMD
mean: 568.9857 us, lb 568.5819 us, ub 569.4641 us
benchmarking primes''TMD
mean: 642.5665 us, lb 642.0495 us, ub 643.4105 us
While I see you are doing this for your own education, its worth noting the related links of Primes on Haskell.org and the fast Primes package on hackage.