Hi Daniel, I haven't yet absorbed everything you've written. One thing though, I didn't know how long division takes, but yeah, obviously gcd would take longer. Also when I put in the correction based on Luke's note, I found out about the perfect square problem. With regard to style, thanks for the suggestions, I'll have to spend a little more time going over that. This was my first posting to this list, and you and your colleagues have given me a real boost. Thanks so much, Mitchell -----Original Message----- From: daniel.is.fischer@web.de [mailto:daniel.is.fischer@web.de] Sent: Sunday, April 25, 2010 4:47 AM To: haskell-cafe@haskell.org Cc: mitchell@kaplan2.com Subject: Re: [Haskell-cafe] I need help getting started Am Sonntag 25 April 2010 06:34:32 schrieb mitchell@kaplan2.com: Luke already explained the type error, so I'll focus on the implementation.
Hi,
I'm just starting to learn, or trying to learn Haskell. I want to write a function to tell me if a number's prime. This is what I've got:
f x n y = if n>=y
Since you call it with y = floor (sqrt (fromIntegral x)), the test ought to be "n > y" or you'll classify squares of primes as primes. PrimeTest> primeQ 25 True Oops.
then True else if gcd x n == 1
This is doing a lot of unnecessary work. If gcd x n > 1, then one of the prime divisors of n must also divide x. If n is composite, this test is never reached, otherwise (n is prime) n divides x, so you need only test whether n divides x, if x `rem` n /= 0 This test needs only one division, whereas calculating the gcd needs O(log n) divisions on average. For larger primes, that's a big difference: Prelude PrimeTest> primeF 1000000000039 True (0.27 secs, 85607928 bytes) Prelude PrimeTest> primeQ 1000000000039 True (1.38 secs, 457966212 bytes)
then f x (n+1) y else False
A stylistic remark, if condition then True else somethingMore is often better expressed as condition || somethingMore or using guards, so you could write f as f x n y = (n > y) || (x `rem` n /= 0 && f x (n+1) y) or f x n y | n > y = True | x `rem` n == 0 = False | otherwise = f x (n+1) y
primeQ x = f x 2 y where y = floor(sqrt(x))
The compiler is very unhappy. Apparently there's some ambiguity in this, and I'm kind of running around in circles. I'd appreciate any help that will get me started.