Boolean Primes Map (continued)

[Hannah Schroeter]

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.