On Tue, 19 Dec 2000, Simon Peyton-Jones wrote:
| Another way to do this is to compute the final array directly,
| instead of computing successive versions of the array:
|
| import Array
| primes n = [ i | i - [2 ..n], not (primesMap ! i)] where
| primesMap = accumArray (||)
There are numerous ways of optimising sieving for primes, none of which have much
to do with this list. For example, two suggestions:
(1) for each k modulo 2*3*5*7, if k is divisible by 2/3/5 or 7, ignore, otherwise
sieve separately for this k on higher primes. (Or you might use products of
There are numerous ways of optimising sieving for primes, none of which
have much to do with this list. For example, two suggestions:
(1) for each k modulo 2*3*5*7, if k is divisible by 2/3/5 or 7, ignore, otherwise
sieve separately for this k on higher primes. (Or you might use
| Another way to do this is to compute the final array directly,
| instead of computing successive versions of the array:
|
| import Array
| primes n = [ i | i - [2 ..n], not (primesMap ! i)] where
| primesMap = accumArray (||) False (2,n) multList
| multList= [(m,True)
On Fri 15 Dec, Shlomi Fish wrote:
There is a different algorithm which keeps a boolean map which tells whether
the number at that position is prime or not. At start it is initialized to all
trues. The algorithm iterates over all the numbers from 2 to the square root
of the desired bound, and
Your algorithm seems to be based on the following idea:
calculate the non-primes and derive the primes from
them by calculating the set difference of the natural numbers
and the non-primes.
A naive implementation of this idea can be found as
primes'
in the attachached file. The function
On Sun 17 Dec, Adrian Hey wrote:
You can use a variation of this algorithm with lazy lists..
primes = 2:(get_primes [3,5..])
get_primes (x:xs) = x:(get_primes (strike (x+x) (x*x) xs))
^^^
Whoops,_|
Shlomi Fish wrote:
As some of you may know, a Haskell program that prints all the primes can be
as short as the following:
primes = sieve [2.. ] where
sieve (p:x) = p : sieve [ n | n - x, n `mod` p 0 ]
Now, this program roughly corresponds to the following perl program:
[ ~20
Hi!
As some of you may know, a Haskell program that prints all the primes can be
as short as the following:
primes = sieve [2.. ] where
sieve (p:x) = p : sieve [ n | n - x, n `mod` p 0 ]
Now, this program roughly corresponds to the following perl program:
## SNIP SNIP #
