[Haskell-beginners] Primes calculation
Daniel Fischer
daniel.is.fischer at web.de
Fri Mar 12 16:28:31 EST 2010
Am Freitag 12 März 2010 22:14:00 schrieb legajid:
> Hi,
> i'm trying to write a function to find all primes from 2 to N.
>
Many examples at http://www.haskell.org/haskellwiki/Prime_numbers
>
> My idea is :
> take the first number (2)
> try to find whether it's a multiple of one of all existing primes
> ([] at first)
> add 2 to the list of primes
>
> take the following number (3)
> find if multiple of existing primes ([2])
> add 3 to the list of primes
>
> take the following number (4)
> find if multiple of existing primes ([2, 3])
> do not add 4 to the list of primes
>
> ...
>
> take the following number (8)
> find if multiple of existing primes ([2, 3, 5, 7])
> do not add 8 to the list of primes
>
> take the following number (9)
> find if multiple of existing primes ([2, 3, 5, 7])
> do not add 9 to the list of primes (multiple of 3)
>
> and so on...
>
> So, i would like a function like :
>
> f (x : xs) = g x : f xs
>
> g would return x if x is prime, [] otherwise
>
> But g would use the preceding value of f (list of primes before the
> calculation for x) that is a result of g itself.
So g would need the list of primes [found so far] as a parameter (without
that, it would need to check whether x is prime from scratch).
If you're not committed to performance, what about simple trial division:
trialDivPrime :: [Integer] -> Integer -> Bool
trialDivPrime (p:ps) n
= (n < p*p) || (n `mod` p /= 0 && trialDivPrime ps n)
isPrime = trialDivPrime primes
primes = 2:filter isPrime [3, 5 .. ]
If you're after performance, a bit-sieve (STUArray) is what you want.
> f needs g that needs f : what's wrong with my mind ?
> Perhaps i am still under control of imperative programming ?
>
> Thanks for your help,
>
> Didier.
More information about the Beginners
mailing list