Nested loops and classic problems in Python

Why this matters

Many real questions compare every item with every other item. Find two students with the same birthday. Check every pair of seats in a cinema for a clash. Draw a grid of cells on a screen. Sort a list by repeatedly comparing neighbours. Each of these needs a loop inside a loop: the outer loop picks an item, and the inner loop looks at the others.

Nested loops are also where beginners first meet speed problems. A program with one loop over a thousand items is fast. A program with two nested loops over a thousand items does a million steps, and a program over a hundred thousand items does ten billion. Learning to count the inner work is the most useful habit in this lesson, because it tells you whether a solution will finish in time before you run it.

The second half of the lesson uses single and nested loops to solve classic problems: factorial, prime tests, Fibonacci numbers and the greatest common divisor. These problems often come up in introductory interviews, and each one teaches a loop pattern you will reuse.

The idea from first principles

A nested loop is a loop whose body contains another loop. The outer loop runs its body once for each value it takes. Each time the outer body runs, the inner loop runs completely, from its first value to its last. The total work is the number of outer passes multiplied by the number of inner passes, when the inner count does not change.

The computer does this in order. It sets the outer variable to its first value. It runs the inner loop from its first value to its last. It moves the outer variable to the next value. It runs the inner loop again from its first value. This repeats until the outer loop ends. A for loop over range starts again from its first value each time it begins, so the inner loop is a fresh count on each outer pass.

Here is the important consequence. Anything in the outer body that is outside the inner loop runs once per outer pass. Anything in the inner body runs once per inner pass, which is once per pair of values. Put the work in the right loop, and the program does only the work it needs.

An everyday analogy: a clock

Think of a clock with an hour hand and a minute hand. For each hour, the minute hand moves through 60 positions, from 0 to 59. The hour is the outer loop and the minute is the inner loop. In a 12-hour cycle, the minute hand goes round 12 times, and each full round is a complete inner loop.

If you wrote a program to print every minute of a day, the outer loop would be the hours, from 0 to 23, and the inner loop would be the minutes, from 0 to 59. In Python that is range(24) for the hours and range(60) for the minutes. The total output is 24 times 60, which is 1440 lines. Each line is printed by the inner body, once per minute. You can count the work without running the program, and that count is what this lesson teaches you to do.

Worked example 1: a grid of products

The simplest nested loop prints a table. The outer loop chooses the row, and the inner loop chooses the column. Each cell is the row number times the column number. This program prints a 3 by 4 grid, with a tab between the values.

The output is:

1	2	3	4	
2	4	6	8	
3	6	9	12	

Trace the first row. The outer variable i is 1. The inner loop runs for j equal to 1, 2, 3 and 4, printing 1, 2, 3 and 4, each followed by a tab. When the inner loop ends, the plain print() moves to a new line. Then i becomes 2 and the inner loop runs again from j equal to 1, printing 2, 4, 6 and 8.

The end="\t" part and the plain print() are the key to the layout. The inner loop uses end="\t" so the values stay on one line. The print() after the inner loop runs once per row, and it moves the cursor down. Python's print ends each call with a newline unless you change end. If you leave out end="\t" inside the inner loop, every value is printed on its own line, and the table no longer looks like a grid. This is the most common output mistake with nested loops.

The inner body ran 3 times 4, which is 12 times, and the output has 12 numbers. Counting the inner body is the first step of the complexity analysis that follows.

Counting the work

The number of times the innermost body runs is the total work. For a grid with rows rows and cols columns, the work is rows times cols. For two loops that both run n times, the work is n times n, which is n squared. Write that as O(n squared), which reads as "proportional to n squared".

Big O notation describes how the work grows as the input grows. It ignores the exact numbers and keeps only the part that grows fastest. An O(n squared) program that does 2 times n squared steps and an O(n squared) program that does 5 times n squared steps are both O(n squared), because the growth shape is the same. In practice, the constant matters too, but the shape decides whether a program will finish for large inputs.

Here is a useful table. It shows why the shape matters so much.

At one hundred thousand items, the one-loop program does 100000 steps, which is instant. The nested program does ten billion steps, which may take many seconds or minutes. Interviewers ask about this because the same problem can have an O(n squared) answer and an O(n) answer, and the difference decides whether the program is usable.

A triangle of work

The inner loop does not always run the same number of times. Consider this program:

count = 0
for i in range(1, 5):
    for j in range(1, i + 1):
        count += 1
print(count)

The outer variable i is 1, 2, 3 and 4. The inner loop runs i times each pass, so it runs 1, 2, 3 and 4 times. The inner range(1, i + 1) stops before i + 1, so it gives exactly i values. The total is 1 + 2 + 3 + 4, which is 10. The output is 10.

The sum of the first n counting numbers has a formula: n times n plus 1, divided by 2. For n equal to 4, that is 4 times 5 divided by 2, which is 10. So the work is about n squared divided by 2, which is still O(n squared), because the constant half does not change the shape. This triangle shape is very common in nested loops. The inner loop shrinks or grows as the outer loop moves, and you should always check its start and end.

How big can n be?

Counting work tells you whether a solution will finish. A rough rule helps, but the number depends on the language. Python runs a loop more slowly than a compiled language does, so the yardstick is lower. On the machine used to check this lesson, a loop that added 1 to a counter 100 million times took about 4.8 seconds. Your machine will give a different number.

For one loop, a limit of 10 million items is fine, which takes about half a second on that machine. For two nested loops, the work is about n squared. Up to about n equal to 3000, the work is about 9 million steps, which is fine. At n equal to 10000, the nested version does 100 million steps, and it took about 4.0 seconds on the same machine. At n equal to 100000, the nested version does 10 billion steps, which would take several minutes at that speed. A problem that gives n up to 100000 is a signal that the nested loop is wrong and a faster method is needed, such as sorting first, or using a table that remembers what was seen.

This is the reason the nested-loop pair count in the module assignment, which is the next lesson, is correct but slow for large inputs. It is a good first answer, and then a better one is the next step. Interviewers want to hear you name the slow version, state its cost, and then improve it.

Worked example 2: a triangle of stars

A triangle pattern is a good drill for nested loops. The outer loop chooses the row. The inner loop prints one star for each column up to the row number. The program reads the number of rows from input. Give it 4.

rows = int(input())
for row in range(1, rows + 1):
    for col in range(1, row + 1):
        print("*", end="")
    print()

Input: 4

The output is:

*
**
***
****

The inner loop's end depends on the outer variable. The line range(1, row + 1) means row 1 prints one star, row 2 prints two, and so on. Each time the inner for starts, col begins again at 1, so there is no reset to write. If you wrote the inner loop with a while loop and a counter, you would have to set the counter back to 1 yourself at the start of each row. Forgetting that reset is a common bug in the while version, and the for version avoids it.

To make a right-aligned triangle, add spaces before the stars. The inner loop for spaces would run rows - row times. Try it as an exercise. It is the first example where you need two inner loops in the same row.

Worked example 3: bubble sort with nested loops

Sorting a list is the classic use of nested loops. The simplest method is bubble sort. It walks along the list comparing neighbours. When two neighbours are out of order, it swaps them. After one full walk, the largest value has bubbled to the end. The walk is then repeated for the rest of the list, and each walk is shorter by one, because the end is already in place.

The outer loop counts the passes. The inner loop does the comparisons for one pass. The inner loop stops one place earlier each time, because the values at the end are already sorted.

Watch bubble sort work in the visualizer below. Look at how the largest value moves to the right end after the first pass.

The next program sorts a list that you type in. It also counts the swaps. The input is two lines: 5, then 5 1 4 2 8.

n = int(input())
a = list(map(int, input().split()))
swaps = 0
for pass_number in range(n - 1):
    for j in range(n - 1 - pass_number):
        if a[j] > a[j + 1]:
            a[j], a[j + 1] = a[j + 1], a[j]
            swaps += 1
print(*a)
print("Swaps:", swaps)

Input:

5
5 1 4 2 8

The output is:

1 2 4 5 8
Swaps: 4

Three details in this code are specific to Python. The line a[j], a[j + 1] = a[j + 1], a[j] swaps two values in one step. Python works out the right side first, so the two values change places, and no temporary variable is needed. The name pass_number is used on purpose, because pass is a reserved word in Python with a meaning of its own, and it cannot be a variable name. The last line, print(*a), prints every value in the list, separated by spaces.

Trace the first pass. The list is 5, 1, 4, 2, 8. The first comparison is 5 with 1. Since 5 is larger, they swap, giving 1, 5, 4, 2, 8. The second comparison is 5 with 4. They swap, giving 1, 4, 5, 2, 8. The third comparison is 5 with 2, which swaps to give 1, 4, 2, 5, 8. The fourth comparison is 5 with 8, which is in order, so nothing changes. The largest value, 8, is at the end. That is one pass, with three swaps.

The second pass compares only up to index 2 because the inner loop stops at n - 1 - pass_number, which is 3 for pass_number equal to 1. It finds 4 with 2, which swaps, giving 1, 2, 4, 5, 8. That is the fourth swap, and the list is sorted. The remaining passes do no swaps, but the program still runs them, because bubble sort in this form does not know the list is sorted. You will see how to stop early in the exercises and the complexity section.

The swap count is 4. That number has a meaning. In a list, a pair of positions where the left value is larger than the right value is called an inversion. Bubble sort swaps exactly once for each inversion, so the swap count is the number of inversions. The list 5, 1, 4, 2, 8 has four inversions: (5, 1), (5, 4), (5, 2) and (4, 2). This is an interview fact you can state, and it shows you understand what the loop is counting.

Why the inner loop shrinks

The inner loop's end is n - 1 - pass_number. On the first pass, the comparisons run from index 0 to index n minus 2. On the second pass, they stop one index earlier. Each pass puts the largest unsorted value into its final place at the right end, so the next pass can ignore it. Without this shrink, the program would still be correct but would do more comparisons than needed. The shrink changes the count from n times n to about n times n divided by 2, which is still O(n squared), but it is a real saving.

The complexity of bubble sort

The number of comparisons is about n times n divided by 2. The number of swaps is the number of inversions, which can be as large as n times n divided by 2 when the list starts in reverse order. So the worst case time is O(n squared). The best case, when the list is already sorted, is O(n) if you stop the program as soon as a whole pass makes no swaps. The memory use is O(1), because the swap uses no extra list and only a few variables. Bubble sort is simple and useful for learning, but it is slow for large lists. The sorting module covers faster methods, and Python's built-in sorted function uses one of them.

Selection sort: fewer swaps

Selection sort is the second sort in this lesson, and it uses the same two loops in a different way. The outer loop fixes one position at a time, from left to right. For position i, the inner loop looks through the rest of the list to find the smallest value, then swaps that value into position i. After the outer loop has visited every position, the list is sorted.

Selection sort makes the choice of swap explicit. Bubble sort swaps whenever two neighbours are out of order, which can happen many times for one value. Selection sort makes at most one swap per pass, so the number of swaps is at most n minus 1. That is useful when a swap is expensive, such as when the values are large records. The number of comparisons is still about n times n divided by 2, and that count does not depend on the input. Even a sorted list makes the same comparisons.

Watch the sorted part grow on the left, and the search for the smallest value on the right, in the visualizer below.

The program below sorts a list you type in and counts the swaps. The input is two lines: 5, then 64 25 12 22 11.

n = int(input())
a = list(map(int, input().split()))
swaps = 0
for i in range(n - 1):
    smallest = i
    for j in range(i + 1, n):
        if a[j] < a[smallest]:
            smallest = j
    if smallest != i:
        a[i], a[smallest] = a[smallest], a[i]
        swaps += 1
print(*a)
print("Swaps:", swaps)

Input:

5
64 25 12 22 11

The output is:

11 12 22 25 64
Swaps: 3

Trace the first pass. Position 0 holds 64. The inner loop scans 25, 12, 22 and 11, and the smallest is 11 at index 4. The program swaps 64 and 11, so the list becomes 11, 25, 12, 22, 64, and the count is 1. The second pass fixes position 1. The smallest of 25, 12, 22 and 64 is 12, so it swaps with 25, making 11, 12, 25, 22, 64, and the count is 2. The third pass finds 22 and swaps it with 25. The fourth pass looks at 25 and 64, finds that 25 is already in place, and makes no swap. The count stays at 3.

Notice the if smallest != i: check. It avoids a swap of a value with itself. Without the check, the program still gives the right answer, but it counts a swap that did nothing, and the count would be wrong. The check is also the reason the swap count is a meaningful measure.

Selection sort has the same worst-case time as bubble sort, O(n squared), and it uses O(1) extra space. Its advantage is the small number of swaps, not speed in general. Insertion sort is usually faster on nearly sorted data, and selection sort is a good choice only when writes are the expensive part of the work.

Insertion sort: another nested-loop sort

A different sort uses the same two-loop shape. Insertion sort works like sorting a hand of playing cards. You take one card at a time and slide it left into the right place among the cards you have already sorted. The outer loop picks the next card, and the inner loop moves it left until it is in place.

Watch the visualizer. Notice how the sorted part at the left grows by one each pass, and how each new value slides left until it fits.

Insertion sort is often faster than bubble sort in practice, because it stops moving a value as soon as the value is in place. For a list that is already nearly sorted, it does very little work. Its worst case is still O(n squared), but its best case is O(n), when the list is already sorted, because the inner loop never moves anything. Interviewers like this comparison, because it shows that two sorts with the same worst case can behave very differently on real data.

Worked example 4: counting primes

A prime is a whole number greater than 1 that is divisible only by 1 and itself. The number 2 is the first prime, and 3, 5 and 7 follow. The number 1 is not prime, and neither is 0. To count primes up to a limit, you need two loops: the outer loop walks over the candidate numbers, and the inner loop tries to divide each candidate by smaller numbers.

The test for one number is simple. A number k is not prime if some d between 2 and k minus 1 divides it exactly. You do not need to try every d. If k has a divisor larger than its square root, then it also has a matching divisor smaller than the square root. So you can stop the inner loop at the square root of k. In Python, math.isqrt(k) gives the whole-number square root, which is 3 for k equal to 9 and 9 for k equal to 97. The range then goes up to that value, plus 1, because range stops before its end.

Type 100 when the program asks for input. The program counts the primes from 2 to 100.

import math
 
limit = int(input())
count = 0
for k in range(2, limit + 1):
    prime = True
    for d in range(2, math.isqrt(k) + 1):
        if k % d == 0:
            prime = False
            break
    if prime:
        count += 1
print(f"Primes up to {limit}: {count}")

Input: 100

The output is:

Primes up to 100: 25

Trace a few candidates. For k equal to 2, math.isqrt(2) is 1, so range(2, 2) is empty and the inner loop does not run at all. The number 2 stays prime. For k equal to 9, the inner loop tries d equal to 2, then 3. The remainder of 9 divided by 3 is 0, so prime becomes False and the break ends the inner loop early. For k equal to 97, the inner loop tries d from 2 up to 9, since math.isqrt(97) is 9. No divisor is found, so 97 is counted.

The break is an early exit, the same tool from the earlier loop lessons. Without it, the inner loop would keep going and check every divisor up to the square root. With it, a composite number stops at its smallest factor. The answer is still correct, and the program is faster.

The work here is harder to count than in the grid example, because the inner loop stops early for most numbers. The worst case is a prime, where the inner loop runs all the way to the square root. The total work for all candidates up to n is roughly n times the square root of n, which is written O(n times sqrt n). That is much better than O(n squared), and it is why trial division is fast enough for small limits.

Worked example 5: factorial with arbitrary-size integers

The factorial of n, written n!, is the product of the whole numbers from 1 to n. Five factorial is 1 times 2 times 3 times 4 times 5, which is 120. Zero factorial is defined as 1. A loop computes it by multiplying a running total by each number in turn.

The next program prints the factorials from 1 to 20, then the factorials of 21 and 30. The answer grows very fast. A Python int has no fixed size. It takes as much memory as the value needs, so every product is exact. The math module also has a factorial function that returns the same values. The loop shows the idea, and the function is what you would use in real code.

The output is:

1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880
10! = 3628800
11! = 39916800
12! = 479001600
13! = 6227020800
14! = 87178291200
15! = 1307674368000
16! = 20922789888000
17! = 355687428096000
18! = 6402373705728000
19! = 121645100408832000
20! = 2432902008176640000
21! = 51090942171709440000
30! = 265252859812191058636308480000000

Readers who know a fixed-size integer type may expect the product to wrap around past about 2 billion, as 13 factorial would in a 32-bit value. Python does not wrap around, so there is no silent wrong answer to guard against. The cost is that big values take more memory and more time to multiply. For a loop like this one, the values stay small enough that the cost does not matter.

Worked example 6: Fibonacci and the greatest common divisor

The Fibonacci sequence starts with 0 and 1. Each later value is the sum of the two before it. The first ten values are 0, 1, 1, 2, 3, 5, 8, 13, 21 and 34. A loop keeps the last two values in variables and moves them forward each pass.

The program below prints the first ten Fibonacci numbers, then the greatest common divisor of 48 and 18. It has one loop for each part. The Fibonacci loop is a single loop, and the GCD loop uses the remainder method from the earlier loop lessons. The last line checks the result against math.gcd.

The output is:

0 1 1 2 3 5 8 13 21 34 
GCD of 48 and 18: 6
math.gcd gives: 6

The line a, b = b, a + b is the Python way to move two values forward. Python works out the whole right side before it assigns anything, so a + b uses the old values of a and b. That is why no temporary variable is needed. The GCD line x, y = y, x % y works the same way.

Trace the Fibonacci loop for the first three passes. Start with a = 0 and b = 1. The first pass prints 0, then a becomes 1 and b becomes 0 + 1, which is 1. The second pass prints 1, then a becomes 1 and b becomes 1 + 1, which is 2. The third pass prints 1, then a becomes 2 and b becomes 3. The values printed match the sequence.

The Fibonacci computation is O(n) time and O(1) space, because it keeps only two values. A recursive version, where the function calls itself, is short to write, but it does far more work, because the same smaller values are computed again and again. Python also limits how deep a recursive call chain may go. The default limit is 1000 calls, and a function that goes deeper stops with RecursionError. Interviewers often ask for both versions, so keep the loop in mind as the efficient answer.

Common mistakes with nested loops

Using the same variable name in both loops

In Python this is not an error. The program runs, but the outer variable is overwritten by the inner loop. The example below is meant to print 0, 1 and 2, one per line, after each inner loop finishes:

for i in range(3):
    for i in range(2):
        pass
    print(i)

The output is:

1
1
1

Python does not warn you. The outer loop still runs three times, because for takes its next value from range(3), not from i. But after each inner loop, i holds the inner loop's last value, which is 1. So the output is wrong without any message. The fix is a different name for each loop variable, such as i for the outer loop and j for the inner loop.

Indentation that does not match

Python uses indentation to show which lines belong to a loop. A loop body must be indented more than the for line. This program has no indented body:

for i in range(3):
print(i)

Python stops with this error:

    print(i)
    ^^^^^
IndentationError: expected an indented block after 'for' statement on line 1

The traceback also shows the file name and the line number above these lines. The opposite mistake, a line indented too far, gives a different message:

for i in range(3):
    print(i)
        print("x")

IndentationError: unexpected indent

Read the line number in the message, then check that the body lines all use the same indent.

Printing with print inside the inner loop

As described above, print(i) inside the inner loop puts each value on its own line. Use end="" in the inner loop, then a plain print() after it.

Breaking out of the wrong loop

A break inside the inner loop stops only the inner loop. The prime counter uses this on purpose, because a composite number needs only one divisor to be rejected. Python has no labels, so there is no break that leaves two loops at once. To leave both loops, put them inside a function and use return. The return ends the function, and that ends both loops.

Expecting the inner loop to pick up where it stopped

The inner loop's start is set again each time the outer loop runs. If you need the inner loop to continue from where it left off, the design is different, and you should use one loop with a clear rule instead.

Changing a list while looping over it

A common beginner mistake is removing items from a list inside a for loop over that same list. This program was meant to remove the even numbers:

a = [2, 4, 6]
for x in a:
    if x % 2 == 0:
        a.remove(x)
print(a)

The output is:

[4]

When 2 is removed, the list shifts left, so the loop moves on to index 1, which now holds 6. The 4 is skipped. Loop over a copy, such as for x in a[:], or build a new list with the values you want to keep.

Using a decimal number in range

range takes whole numbers only. This line fails:

for i in range(1, 2.5):
    print(i)

TypeError: 'float' object cannot be interpreted as an integer

The value 2.5 is a decimal number. Use a whole number, such as range(1, 3), or compute the whole number first.

Off by one with range

range(1, 4) gives 1, 2 and 3. It stops before 4, which is the same rule that makes range(4) give 0 to 3. The grid example needs range(1, 4) for three rows, and a common error is writing range(1, 3), which gives only two rows.

Using a keyword as a name

pass is a reserved word, so this is a syntax error:

pass = 1

    pass = 1
         ^
SyntaxError: invalid syntax

Python reserves other words for its own use too, such as for, while and in. Pick a name that describes the value, such as pass_number.

Debugging walkthrough: a grid with the wrong numbers

A learner wrote the grid program with the wrong output. It should print the products, but it prints 1 2 3 4 on the first line, then 2 4 6 8 on the second line, and the third line is missing.

Step 1: check the expected output. Row 3 should be 3, 6, 9, 12, so the problem is on the third line.

Step 2: count the rows. If the program prints only two rows, the outer loop ends too early. Check its range, which might be range(1, 3) instead of range(1, 4).

Step 3: test the fix. Change range(1, 3) to range(1, 4), and the third row appears. Check the inner loop as well, which must run for 4 columns.

Step 4: look for a second bug. Suppose the output is now complete, but each value is on its own line. That is the end problem. Check the inner loop's print. It should use end="\t", and the plain print() should sit after the inner loop.

Step 5: the final check. Count the numbers. There should be 12 values. A trace of the first and last row confirms that the grid is correct.

The method is the same as in the earlier lessons. Check the expected values, count the passes, and find the first point where the program differs from your expectation. Nested loops make the count harder, so write the counts down.

Edge cases to check

Nested loops fail on the edges, so test these every time.

A zero-size outer loop: if n is 0, range(0) is empty, so the outer loop does not run and nothing is printed. Check that this is the right answer.

A one-item bubble sort: with n equal to 1, range(n - 1) is empty, so the outer loop runs zero times. The list is already sorted, and the program prints the one value with no swaps.

A list that is already sorted: bubble sort does no swaps, and insertion sort does no moves. Both are correct, and the second is faster.

A list in reverse order: bubble sort does the maximum number of swaps, which is n times n minus 1, divided by 2. A list of 5 values in reverse gives 10 swaps. Use this to test your count.

The prime test on 1 and 0: the loop starts at k equal to 2, so 0 and 1 are never counted. A common error is starting at 1, which counts 1 as prime.

The Fibonacci loop with a count of 0: range(0) runs zero times. Only the final print() runs, and it prints an empty line, which is the right output for an empty sequence.

Interview patterns for nested loops

Interviewers ask nested loop questions in a few standard shapes. Learn them.

The first is the pair search: compare every item with every later item. The inner loop starts at the outer index plus one. The time is O(n squared). You then ask whether a sort or a dictionary could make it faster, which is a later module.

The second is the grid scan: visit every cell of a rows-by-columns grid. The time is O(rows times columns). Interviewers often ask for the first cell that matches. In Python, the way to stop both loops at that cell is a return from a function, as described above.

The third is the triangular count: the inner loop runs i times on pass i. The total is about n squared divided by 2. Know the formula, and be able to explain why the constant does not change the O(n squared) shape.

The fourth is the single loop with a running value, such as the factorial or Fibonacci. It is O(n) and needs O(1) extra space. Many interview answers are a single loop, and the skill is in choosing which values to keep.

When you explain your answer, say the loop count in words, then give the big O. For example, "the outer loop runs n times and the inner loop runs about n times, so the work is about n squared."

Real-world uses

Nested loops appear in almost every program that works on a table or a grid. A spreadsheet recalculates each cell by looking at its row and column. An image filter visits every pixel and, for each pixel, looks at its neighbours. A timetable program checks every pair of classes for a clash. A game checks every pair of objects on the screen for a collision. A sort inside a program, even a small one, is almost always a nested loop, and knowing its cost stops you from using a slow method on a large list.

The key skill in all these cases is to count the inner work before you write the code. Decide whether the work is small enough. If it is not, look for a way to reduce one of the loops, such as sorting first or stopping early.

Practice

Try each exercise before you open the answer. For each nested loop, write the loop count in words before you run it.

1. Print the numbers 1 to 100 that are prime. Wrap the prime test from this lesson in an outer loop.
2. Print the first ten factorials in a table, one per line, with the number and its factorial.
3. Print the multiplication tables from 1 to 5. Each table should have 10 rows, and a blank line should follow each table.
4. Read a number n and print a right-aligned triangle of stars, n rows high. Use one inner loop for spaces and one for stars.
5. Read a list of numbers and count how many pairs of positions have equal values. Use nested loops and count each pair once.
6. Modify bubble sort so it stops as soon as a whole pass makes no swaps. Count the passes it runs for the list 1 2 3 4 5, which is 1.
7. Print every pair (i, j) with i less than j, both from 1 to 4. Count the pairs. The answer is 6.
8. Print the first 15 Fibonacci numbers in a single row, separated by spaces.
9. Read a number and print the number of digits in its factorial, using a loop that multiplies the values and then counts the digits. Test with 5 and 10. The factorial of 5 has 3 digits and the factorial of 10 has 7.
10. Find the number of inversions in a list of 5 values by comparing every pair. Check it against the bubble sort swap count for the same list.

Exercises 4, 5, 9 and 10 read input. The others print directly.

Show the answer

# 1
import math
for k in range(2, 101):
    prime = True
    for d in range(2, math.isqrt(k) + 1):
        if k % d == 0:
            prime = False
            break
    if prime:
        print(k)

# 2
fact = 1
for n in range(1, 11):
    fact *= n
    print(n, fact)

# 3
for i in range(1, 6):
    for j in range(1, 11):
        print(f"{i} x {j} = {i * j}")
    print()

# 4
n = int(input())
for row in range(1, n + 1):
    for s in range(n - row):
        print(" ", end="")
    for s in range(row):
        print("*", end="")
    print()

# 5
n = int(input())
a = list(map(int, input().split()))
pairs = 0
for i in range(n):
    for j in range(i + 1, n):
        if a[i] == a[j]:
            pairs += 1
print(pairs)

# 6 (the list 1 2 3 4 5 needs 1 pass, and that pass makes no swaps)
a = [1, 2, 3, 4, 5]
n = len(a)
passes = 0
for pass_number in range(n - 1):
    swapped = False
    passes += 1
    for j in range(n - 1 - pass_number):
        if a[j] > a[j + 1]:
            a[j], a[j + 1] = a[j + 1], a[j]
            swapped = True
    if not swapped:
        break
print(passes)

# 7
count = 0
for i in range(1, 5):
    for j in range(i + 1, 5):
        print(f"({i}, {j})")
        count += 1
print(count)

# 8
a, b = 0, 1
for i in range(15):
    print(a, end=" ")
    a, b = b, a + b
print()

# 9
n = int(input())
f = 1
for k in range(2, n + 1):
    f *= k
digits = 0
rest = f
while True:
    # Python has no do-while loop, so this runs the body first, then tests.
    digits += 1
    rest //= 10
    if rest == 0:
        break
print(digits)

# 10
n = int(input())
a = list(map(int, input().split()))
inv = 0
for i in range(n):
    for j in range(i + 1, n):
        if a[i] > a[j]:
            inv += 1
print(inv)
# Bubble sort performs one swap per inversion, so the two counts match.

What this lesson covered

• Nested for loops over range, and how the inner loop restarts on each outer pass.
• Counting the work of a loop, and why O(n squared) becomes slow for large n.
• Bubble sort, selection sort and insertion sort, with their swap and comparison counts.
• Prime tests with math.isqrt, factorial with Python's exact integers, Fibonacci with tuple assignment, and the GCD with a while loop.
• The common mistakes: reused variable names, indentation errors, range with decimals, pass as a name, and changing a list during a loop.

The next lesson is the module assignment. It combines everything in this module into one project.