Problem 1

Compute the Sieve of Eratosthenes.

List all the prime numbers given a limit which are greater than 1 and smaller-equal limit.

Functions:

find(a, x)	Locate the leftmost value in a exactly equal to x.
naive_is_prime(number)	Check naively whether the number is a prime number.
sieve(limit)	Apply the Sieve of Eratosthenes on the numbers up to limit.

find(a: List[int], x: int) → int

Locate the leftmost value in a exactly equal to x.

Return -1 if the element was not found in a.

Ensures

• result != -1 ⇒ 0 <= result < len(a)

naive_is_prime(number: int) → bool

Check naively whether the number is a prime number.

sieve(limit: int) → List[int]

Apply the Sieve of Eratosthenes on the numbers up to limit.

Returns

list of prime numbers till limit

Requires

• limit > 1

Ensures

• len(result) == len(set(result))

  (Unique results)

• all(
      1 < number <= limit
      for number in result
  )
  

• all(
      naive_is_prime(number)
      for number in result
  )