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.