Skip to content

Task 02: Simple Programs

a) Sieve of Eratosthenes

This is a famous algorithm to find prime numbers that was already known in in the 3rd century BCE.

Here is how it works:

  • You start with an empty list of already known primes.
  • Starting with the number 2 and then for all following numbers:
  • Check if the current number can be divided by any of the known primes without remainder
    • If this is the case, the current number can not be prime and you continue with the next number.
    • If all divisions with a preceding prime leave a remainder, the current number is prime as well and is added to the list of known primes.

Use this algorithm to find the 100th prime number.

Hint: Python’s break and continue statements can be of great help in this task.

The algorithm on Wikipedia

b) A Random DNA Sequence

Apologies to all biologists for the extreme simplifications of how DNA works.

Creating a Sequence

Generate a random DNA-like sequence made up of the symbols A, C, G, T. The sequence should be 10.000 (ten thousand) characters long.

Hint: Check the random module from the Python standard library for a useful function to help you.

Extracting Triplets

Split up the sequence into triplets (i.e. sequences with three characters) store all those triplets in a list. If some characters get left over, they can be discarded.

Finding the Good Parts

Go through the list of triplets. If you encounter the triplet AAA all following triplets go into a separate list (let’s say they form the basis for valid genes) until you either encounter AAA again, starting a new list or until you reach the triplet TTT. If the list of triplets ends before a gene-list is completed, that gene is discarded.

No gene-list should contain the AAA or TTT triplets.

Print the amount of found gene-lists, the lengths of each and the total amount of triplets in all genes.