# Prime numbers

11 messages
Open this post in threaded view
|

## Prime numbers

 Hello all, Trying to learn Haskell here... In a Haskell tutorial I found a function deciding if a number is prime: --//-- prime n = not (factors 2 n) factors m n | m == n = False              | m < n  = divides m n || factors (m+1) n divides a b = (mod a b == 0) --//-- Reference: http://www.cs.chalmers.se/Cs/Grundutb/Kurser/d1pt/d1pta/Function%20Definition%20by%20Cases%20and%20Recursion/sld038.htmThis function seems to produce a wrong result on the number 38466629 (warning, slow computation). This number is prime but the function says that it's not. How do I know that 38466629 is prime? Beause: * http://www.rsok.com/~jrm/printprimes.html says that it is. * I wrote another prime function that says that it is. This is my function: --//-- prime 1 = False prime 2 = True prime n = filter (divides n) primes == []                where numbers = [x | x <- [2..n-1], x*x <= n]                      primes  = filter prime numbers divides a b = (mod a b == 0) --//-- I can't figure out what's wrong with the first one. Can anyone spot the problem? (I'm just curious - trying to learn Haskell). Cheers, Daniel. --       /\/`) http://oooauthors.org     /\/_/  http://opendocumentfellowship.org    /\/_/     \/_/    I am not over-weight, I am under-tall.     / _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

## Re: Prime numbers

Open this post in threaded view
|

## Re: Prime numbers

 In reply to this post by Daniel Carrera-2 John Peterson wrote: > Add a type signature: > > prime :: Integer -> Bool > > It's defaulting to Int and you're getting overflows Thanks. Hmm... it's still not working. Btw, I mis-reported the problem. The offending number is 38466629, which is /not/ prime but the sample program reports as prime. 38466629 = 31 * 1240859 The offending program is: --//-- prime :: Integer -> Bool prime n = not (factors 2 n) factors :: Integer -> Integer -> Bool factors m n | m == n = False              | m < n  = divides m n || factors (m+1) n divides :: Integer -> Integer -> Bool divides a b = (mod a b == 0) --//-- The math behind the program seems correct... :( Cheers, Daniel. --       /\/`) http://oooauthors.org     /\/_/  http://opendocumentfellowship.org    /\/_/     \/_/    I am not over-weight, I am under-tall.     / _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

## Re: Prime numbers

 In reply to this post by Jens Fisseler Jens Fisseler wrote: > What about this: 38466629 = 31 x 1240859 Yes, I wrote backwards. The offending program says that it's prime but it's not. Cheers, Daniel. --       /\/`) http://oooauthors.org     /\/_/  http://opendocumentfellowship.org    /\/_/     \/_/    I am not over-weight, I am under-tall.     / _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

## Re: Prime numbers

 In reply to this post by Daniel Carrera-2 Hi Daniel! You just have to change the arguments of the 'mod'-function: old: divides a b = (mod a b == 0) new: divides a b = (mod b a == 0) Regards, Jens _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

## Re: Prime numbers

 In reply to this post by Daniel Carrera-2 Daniel, Could it be that the arguments to either divides or mod should be reversed? Currently it seems to be testing whether the candidate prime (n) divides the possible factor (m). Or am I to tired to read the code straight? Regards, Maarten On 12/20/05, Daniel Carrera <[hidden email]> wrote: > John Peterson wrote: > > Add a type signature: > > > > prime :: Integer -> Bool > > > > It's defaulting to Int and you're getting overflows > > Thanks. Hmm... it's still not working. > > Btw, I mis-reported the problem. The offending number is 38466629, which > is /not/ prime but the sample program reports as prime. > > 38466629 = 31 * 1240859 > > The offending program is: > --//-- > prime :: Integer -> Bool > prime n = not (factors 2 n) > > factors :: Integer -> Integer -> Bool > factors m n | m == n = False >              | m < n  = divides m n || factors (m+1) n > > divides :: Integer -> Integer -> Bool > divides a b = (mod a b == 0) > --//-- > > The math behind the program seems correct... :( > > Cheers, > Daniel. > > > > -- >       /\/`) http://oooauthors.org>      /\/_/  http://opendocumentfellowship.org>     /\/_/ >     \/_/    I am not over-weight, I am under-tall. >     / > _______________________________________________ > Haskell-Cafe mailing list > [hidden email] > http://www.haskell.org/mailman/listinfo/haskell-cafe> _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

## Re: Prime numbers

 In reply to this post by Daniel Carrera-2 -divides a b = (mod a b == 0) +divides a b = (mod b a == 0) On Dec 20, 2005, at 11:09 AM, Daniel Carrera wrote: > John Peterson wrote: >> Add a type signature: >> prime :: Integer -> Bool >> It's defaulting to Int and you're getting overflows > > Thanks. Hmm... it's still not working. > > Btw, I mis-reported the problem. The offending number is 38466629,   > which is /not/ prime but the sample program reports as prime. > > 38466629 = 31 * 1240859 > > The offending program is: > --//-- > prime :: Integer -> Bool > prime n = not (factors 2 n) > > factors :: Integer -> Integer -> Bool > factors m n | m == n = False >             | m < n  = divides m n || factors (m+1) n > > divides :: Integer -> Integer -> Bool > divides a b = (mod a b == 0) > --//-- > > The math behind the program seems correct... :( > > Cheers, > Daniel. > > > > -- >      /\/`) http://oooauthors.org>     /\/_/  http://opendocumentfellowship.org>    /\/_/ >    \/_/    I am not over-weight, I am under-tall. >    / > _______________________________________________ > Haskell-Cafe mailing list > [hidden email] > http://www.haskell.org/mailman/listinfo/haskell-cafe_______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

## Re: Prime numbers

 In reply to this post by Daniel Carrera-2 Daniel Carrera <[hidden email]> writes: > This function seems to produce a wrong result on the number 38466629 > (warning, slow computation). Here is an easier-to-find problem: it tells me the number 4 is prime. Regards,     Malcolm _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

## Re: Prime numbers

 In reply to this post by Bugzilla from robdockins@fastmail.fm Robert Dockins wrote: > -divides a b = (mod a b == 0) > +divides a b = (mod b a == 0) Oh, thanks. My program assumed one way to define 'divides' and the example assumed the other. When I wrote it I was thinking of (divides a) being a function that tells me if the input divides 'a'. Thanks! Cheers, Daniel. --       /\/`) http://oooauthors.org     /\/_/  http://opendocumentfellowship.org    /\/_/     \/_/    I am not over-weight, I am under-tall.     / _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe