Primes calculation

legajid

12 Mar 2010 12 Mar '10

9:14 p.m.

Hi, i'm trying to write a function to find all primes from 2 to N. 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. 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.

Show replies by date

Daniel Fischer

12 Mar 12 Mar

9:28 p.m.

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.

Ozgur Akgun

13 Mar 13 Mar

3:49 a.m.

If we try to implement your idea literally we would need one more parameter to the function: the list of existing primes. I'll call this function primesWRT, since it finds all primes, with respect to the second list provided. primesWRT [] _ = [] -- base case primesWRT (x:xs) existing -- if all x is not divided by all of the existing primes, -- x itself is a prime (wrt 'existing') -- add it to the primes list, and the existing primes list for the next function call | all (\ y -> mod x y /= 0 ) existing = x : primesWRT xs (x:existing) -- if x is not prime, check the rest. | otherwise = primesWRT xs existing primes xs = primesWRT xs [] Please keep in mind that this function assumes its parameter to be in form [2..n]. But this is an assumption coming from your description. primes [2..20] = [2,3,5,7,11,13,17,19] primes [2..30] = [2,3,5,7,11,13,17,19,23,29] primes [10..30] = [10,11,12,13,14,15,16,17,18,19,21,23,25,27,29] -- not bad actually, works as advertised. Best, On 12 March 2010 21:14, legajid wrote:

...

Hi, i'm trying to write a function to find all primes from 2 to N.

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. 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.

_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners

-- Ozgur Akgun

Sriram Durbha

6:32 a.m.

...

primes [10..30] = [10,11,12,13,14,15,16,17,18,19,21,23,25,27,29] -- not bad actually, works as advertised.

10 is not prime. On Fri, Mar 12, 2010 at 7:49 PM, Ozgur Akgun wrote:

...

If we try to implement your idea literally we would need one more parameter to the function: the list of existing primes. I'll call this function primesWRT, since it finds all primes, with respect to the second list provided.

primesWRT [] _ = [] -- base case primesWRT (x:xs) existing -- if all x is not divided by all of the existing primes, -- x itself is a prime (wrt 'existing') -- add it to the primes list, and the existing primes list for the next function call | all (\ y -> mod x y /= 0 ) existing = x : primesWRT xs (x:existing) -- if x is not prime, check the rest. | otherwise = primesWRT xs existing

primes xs = primesWRT xs []

Please keep in mind that this function assumes its parameter to be in form [2..n]. But this is an assumption coming from your description.

primes [2..20] = [2,3,5,7,11,13,17,19] primes [2..30] = [2,3,5,7,11,13,17,19,23,29] primes [10..30] = [10,11,12,13,14,15,16,17,18,19,21,23,25,27,29] -- not bad actually, works as advertised.

Best,

On 12 March 2010 21:14, legajid wrote:

...
Hi, i'm trying to write a function to find all primes from 2 to N.

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. 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.

_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners

-- Ozgur Akgun

_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners

I. J. Kennedy

6:39 a.m.

...

primes [10..30] = [10,11,12,13,14,15,16,17,18,19,21,23,25,27,29] -- not bad actually, works as advertised.

FAIL

Ozgur Akgun

9:55 a.m.

Yes, the function fails for [10..30]. But do you ever read the explanations? On 13 March 2010 06:39, I. J. Kennedy wrote:

...

primes [10..30] = [10,11,12,13,14,15,16,17,18,19,21,23,25,27,29] -- not bad

...
actually, works as advertised.

FAIL

-- Ozgur Akgun

Daniel Fischer

12:47 p.m.

Am Samstag 13 März 2010 10:55:59 schrieb Ozgur Akgun:

...

Yes, the function fails for [10..30]. But do you ever read the explanations?

You probably should have chosen another signature for primes, primes n = primesWRT [2 .. n] [] , to avoid the misunderstandings.

Ozgur Akgun

1:02 p.m.

Yes you're right. I tried to implement sth to answer the original question. Not something I came up with. On 13 March 2010 12:47, Daniel Fischer wrote:

...

Am Samstag 13 März 2010 10:55:59 schrieb Ozgur Akgun:

...
Yes, the function fails for [10..30]. But do you ever read the explanations?

You probably should have chosen another signature for primes,

primes n = primesWRT [2 .. n] []

, to avoid the misunderstandings.

-- Ozgur Akgun

5592

Age (days ago)

5593

Last active (days ago)

List overview

Download

7 comments

5 participants

participants (5)

Daniel Fischer
I. J. Kennedy
legajid
Ozgur Akgun
Sriram Durbha