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.
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.