[Haskell-cafe] I need help getting started
Daniel Fischer
daniel.is.fischer at web.de
Sun Apr 25 04:46:38 EDT 2010
Am Sonntag 25 April 2010 06:34:32 schrieb mitchell at 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.
More information about the Haskell-Cafe
mailing list