Hello!

On Fri, Dec 22, 2000 at 05:58:56AM +0200, Shlomi Fish wrote:

> primes :: Int -> [Int]
> primes how_much =  (iterate 2 initial_map) where
>       initial_map :: [Bool]
>       initial_map = (map (\x -> True) [ 0 .. how_much])
>       iterate :: Int -> [Bool] -> [Int]
>       iterate p (a:as) | p > mybound = process_map p (a:as)
>                        | a = p:(iterate (p+1) (mymark (p+1) step (2*p) as))
>                        | (not a) = (iterate (p+1) as) where
>                               step :: Int
>                               step = if p == 2 then p else 2*p
>         mymark :: Int -> Int -> Int -> [Bool] -> [Bool]
>         mymark cur_pos step next_pos [] = []
>         mymark cur_pos step next_pos (a:as) = 
>               if (cur_pos == next_pos) then
>                       False:(mymark (cur_pos+1) step (cur_pos+step) as)
>               else
>                       a:(mymark (cur_pos+1) step next_pos as)
>       mybound :: Int
>       mybound = ceiling(sqrt(fromIntegral(how_much)))
>       process_map :: Int -> [Bool] -> [Int]
>       process_map cur_pos [] = []
>       process_map cur_pos (a:as) | a = cur_pos:(process_map (cur_pos+1) as)
>                                  | (not a) = (process_map (cur_pos+1) as)

This is buggy.

hannah@mamba:~/src/haskell $ ./primes3 100
[2,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39,41,43,45,47,49,51,53,55,57,59,61,63,65,67,69,71,73,75,77,79,81,83,85,87,89,91,93,95,97,99,101]
51 primes found.

Correct result is:
hannah@mamba:~/src/haskell $ ./primes0 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]
25 primes found.

And it's much slower than your previous, correct variant as well as
my just-mailed variant.

Kind regards,

Hannah.

_______________________________________________
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe

Reply via email to