Prime numbers

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
11 messages Options
Reply | Threaded
Open this post in threaded view
|

Prime numbers

Daniel Carrera-2
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.htm

This 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
Reply | Threaded
Open this post in threaded view
|

Re: Prime numbers

Jens Fisseler
Hi Daniel!

> How do I know that 38466629 is prime?

What about this: 38466629 = 31 x 1240859

Regards,

        Jens

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Prime numbers

Daniel Carrera-2
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
Reply | Threaded
Open this post in threaded view
|

Re: Prime numbers

Daniel Carrera-2
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
Reply | Threaded
Open this post in threaded view
|

Re: Prime numbers

Jens Fisseler
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
Reply | Threaded
Open this post in threaded view
|

Re: Prime numbers

Maarten Hazewinkel
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
Reply | Threaded
Open this post in threaded view
|

Re: Prime numbers

Bugzilla from robdockins@fastmail.fm
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
Reply | Threaded
Open this post in threaded view
|

Re: Prime numbers

Malcolm Wallace
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
Reply | Threaded
Open this post in threaded view
|

Re: Prime numbers

Daniel Carrera-2
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
Reply | Threaded
Open this post in threaded view
|

Re: Prime numbers

Daniel Carrera-2
In reply to this post by Daniel Carrera-2
Henning Thielemann wrote:
>>factors :: Integer -> Integer -> Bool
>>factors m n | m == n = False
>>             | m < n  = divides m n || factors (m+1) n
>
>
> Btw. I find the recursion harder to understand than the explicit
> definition:
>
> factors n = any (divides n) [2..(n-1)]

For what it's worth, I also found this function un-intuitive. What I'd
expect a function called "factors" to do is exactly what yours does, and
not what the one in the example does.

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
Reply | Threaded
Open this post in threaded view
|

Re: Prime numbers

Bill Wood-3
On Tue, 2005-12-20 at 16:53 +0000, Daniel Carrera wrote:

> Henning Thielemann wrote:
> >>factors :: Integer -> Integer -> Bool
> >>factors m n | m == n = False
> >>             | m < n  = divides m n || factors (m+1) n
> >
> >
> > Btw. I find the recursion harder to understand than the explicit
> > definition:
> >
> > factors n = any (divides n) [2..(n-1)]
>
> For what it's worth, I also found this function un-intuitive. What I'd
> expect a function called "factors" to do is exactly what yours does, and
> not what the one in the example does.

It helped me to read "factors m n" as "there is an integer between m and
n-1 inclusive that divides n".  Then the recursion made sense.
Thielemann's "factors n" would read "there is an integer between 2 and
n-1 inclusive that divides n".

 -- Bill Wood


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe