Dr Alexander Fletcher
Autumn 2020/21
Last time we were trying to find the factors of all numbers up to 50,000 using trial division and ended up with the following code.
1 2 3 4 5 6 7 8 9 | n = 1 while n <= 50000: print("n =", n) i = 1 while i <= n: if n % i == 0: print(i) i = i + 1 n = n + 1 |
We have subsequently learnt about the for
loop, which will achieve the same as our while
loops in this case. We can refactor the code, that is rewrite it to make it more readable, but without changing the way it works.
The following code is now more readable and easier to understand. This tidying up of the code is like rewriting rough work.
1 2 3 4 5 6 | for n in range(1, 50001): print("n =", n) for i in range(1, n+1): if n % i == 0: print(i) |
This code runs very slowly for big numbers. Can we do anything to speed it up and improve the perfomance? Go back and think about the method we were using.
There are several ways that you can time how long a program takes to run. One way is to import and use the time
module, as follows.
1 2 3 4 5 6 7 | import time start = time.time() # Insert your program here end = time.time() print("This program took", end - start, "seconds") |
(You will learn more about Python modules in Week 6.)
The homework this week is to write a program to draw Pascal's triangle. We will now look at what steps are needed to do that, but we won't produce the Python code.
Task:
Task: Produce detailed written instructions on how to draw the first $n$ lines of Pascal's triangle, for $n\in\mathbb{N}$.
Things you should assume about the reader:
After a short break...
Task: Take a fresh piece of paper and precisely follow the instructions you have been given, using $n = 6$. You should do no more and no less than is written in the instructions.