Week 8: Exercises

1. All Primes

Construct an infinite list containing all prime numbers using the Sieve of Eratosthenes.

2. Greatest Common Divisor

Write a function that computes the greatest common divisor of two numbers. It should work with any integral type, e.g. either Int or Integer.

3. Vector Sum

Write a function add_vec that adds two vectors represented as lists. Give your function the most general possible type.

4. Matrix Addition

Write a function add that adds two matrices represented as lists of lists.

5. Dot Product

Write a function dot that computes the dot product of two vectors represented as lists.

6. Quicksort

Write a function that sorts a list of values using quicksort. Give your function an appropriate type using a type class constraint. When partitioning a list, use the first element as the pivot (which will be very inefficient if the list is already sorted, but that is OK for this exercise).

7. Pythagorean Triples

Write a function triples that takes an integer N and returns a list of integer triples (a, b, c) with 0 < a < b < c ≤ N such that a² + b² = c². If two triples are multiples of each other (e.g. (3, 4, 5) and (6, 8, 10)), only the smaller of them (e.g. (3, 4, 5)) should appear in the list.

> triples 15
[(3,4,5),(5,12,13)]

8. Amicable Numbers

Solve Project Euler's problem 21.

9. 1000-digit Fibonacci Number

Solve Project Euler's problem 25.

10. Quadratic Primes

Solve Project Euler's problem 27.

10. Distinct Powers

Solve Project Euler's problem 29.