# Difference between revisions of "99 questions/31 to 41"

(P39 solved.) |
|||

Line 30: | Line 30: | ||

== Problem 32 == |
== Problem 32 == |
||

− | <Problem description> |
||

+ | (**) Determine the greatest common divisor of two positive integer numbers. |
||

+ | Use Euclid's algorithm. |
||

<pre> |
<pre> |
||

Example: |
Example: |
||

− | <example in lisp> |
||

+ | * (gcd 36 63) |
||

+ | 9 |
||

Example in Haskell: |
Example in Haskell: |
||

− | <example in Haskell> |
||

+ | [myGCD 36 63, myGCD (-3) (-6), myGCD (-3) 6] |
||

+ | [9,3,3] |
||

</pre> |
</pre> |
||

Solution: |
Solution: |
||

<haskell> |
<haskell> |
||

− | <solution in haskell> |
||

+ | gcd' 0 y = y |
||

+ | gcd' x y = gcd' (y `mod` x) x |
||

+ | myGCD x y | x < 0 = myGCD (-x) y |
||

+ | | y < 0 = myGCD x (-y) |
||

+ | | y < x = gcd' y x |
||

+ | | otherwise = gcd' x y |
||

</haskell> |
</haskell> |
||

− | <description of implementation> |
||

+ | The Prelude includes a gcd function, so we have to choose another name for ours. The function gcd' is a straightforward implementation of Euler's algorithm, and myGCD is just a wrapper that makes sure the arguments are positive and in increasing order. |
||

− | |||

+ | |||

== Problem 33 == |
== Problem 33 == |
||

## Revision as of 23:44, 12 December 2006

These are Haskell translations of Ninety Nine Lisp Problems.

If you want to work on one of these, put your name in the block so we know someone's working on it. Then, change n in your block to the appropriate problem number, and fill in the <Problem description>,<example in lisp>,<example in Haskell>,<solution in haskell> and <description of implementation> fields.

## Problem 31

Determine whether a given integer number is prime.

Example: * (is-prime 7) T Example in Haskell: P31> isPrime 7 True

Solution:

```
isPrime :: Integral a => a -> Bool
isPrime p = all (\n -> p `mod` n /= 0 ) $ takeWhile (\n -> n*n <= x) [2..]
```

Well, a natural number p is a prime number iff no natural number n with n >= 2 and n^2 <= p is a divisor of p. That's exactly what is implemented: we take the list of all integral numbers starting with 2 as long as their square is at most p and check that for all these n there is a remainder concerning the division of p by n.

## Problem 32

(**) Determine the greatest common divisor of two positive integer numbers.

Use Euclid's algorithm.

Example: * (gcd 36 63) 9 Example in Haskell: [myGCD 36 63, myGCD (-3) (-6), myGCD (-3) 6] [9,3,3]

Solution:

```
gcd' 0 y = y
gcd' x y = gcd' (y `mod` x) x
myGCD x y | x < 0 = myGCD (-x) y
| y < 0 = myGCD x (-y)
| y < x = gcd' y x
| otherwise = gcd' x y
```

The Prelude includes a gcd function, so we have to choose another name for ours. The function gcd' is a straightforward implementation of Euler's algorithm, and myGCD is just a wrapper that makes sure the arguments are positive and in increasing order.

## Problem 33

<Problem description>

Example: <example in lisp> Example in Haskell: <example in Haskell>

Solution:

```
<solution in haskell>
```

<description of implementation>

## Problem 34

<Problem description>

Example: <example in lisp> Example in Haskell: <example in Haskell>

Solution:

```
<solution in haskell>
```

<description of implementation>

## Problem 35

<Problem description>

Example: <example in lisp> Example in Haskell: <example in Haskell>

Solution:

```
<solution in haskell>
```

<description of implementation>

## Problem 36

<Problem description>

Example: <example in lisp> Example in Haskell: <example in Haskell>

Solution:

```
<solution in haskell>
```

<description of implementation>

## Problem 37

<Problem description>

Example: <example in lisp> Example in Haskell: <example in Haskell>

Solution:

```
<solution in haskell>
```

<description of implementation>

## Problem 38

<Problem description>

Example: <example in lisp> Example in Haskell: <example in Haskell>

Solution:

```
<solution in haskell>
```

<description of implementation>

## Problem 39

A list of prime numbers.

Given a range of integers by its lower and upper limit, construct a list of all prime numbers in that range.

Example in Haskell: P29> primesR 10 20 [11,13,17,19]

Solution 1:

```
primesR :: Integral a => a -> a -> [a]
primesR a b = filter isPrime [a..b]
```

If we are challenged to give all primes in the range between a and b we simply take all number from a up to b and filter the primes out.

Solution 2:

```
primes :: Integral a => [a]
primes = let sieve (n:ns) = n:sieve [ m | m <- ns, m `mod` n /= 0 ] in sieve [2..]
primesR :: Integral a => a -> a -> [a]
primesR a b = takeWhile (<= b) $ dropWhile (< a) primes
```

Another way to compute the claimed list is done by using the *Sieve of Eratosthenes*. The `primes`

function generates a list of all (!) prime numbers using this algorithm and `primesR`

filter the relevant range out. [But this way is very slow and I only presented it because I wanted to show how nice the *Sieve of Eratosthenes* can be implemented in Haskell :)]

## Problem 40

<Problem description>

Example: <example in lisp> Example in Haskell: <example in Haskell>

Solution:

```
<solution in haskell>
```

<description of implementation>