Exercise of Python Learning

「除數」（divisor）是在除法算式中，用來「除」另一個數字（被除數）的數字。以 12 ÷ 4 = 3 為例，被除數是 12，除數是 4，商是 3。若指整數的整除關係，除數在中文也常被稱為「因數」（factor）。

def allPrimesUpTo(num):

    primes = [2]

    for number in range(3, num):

        sqrtNum = number**0.5

        for factor in primes:

            if number % factor == 0:

                break

            if factor > sqrtNum:

                primes.append(number)

                break

    return primes

print(allPrimesUpTo(20))

Function definition

Creates a function that will return all prime numbers less than num.

Initialize list of primes

Starts with [2] because 2 is the first prime number.

This list will grow as new primes are found.

Loop through candidate numbers

Tests every integer from 3 up to num - 1.

Compute square root

Finds the square root of the candidate number.

Check divisibility against known primes

for factor in primes:

Loops through all primes found so far.

This is efficient: instead of checking every integer, you only check prime factors.

Case 1: divisible by a prime

if number % factor == 0:

    break

If number is divisible by any prime factor, it’s not prime.

break exits the loop immediately.

Case 2: factor exceeds square root

if factor > sqrtNum:

    primes.append(number)

    break

If you’ve checked all prime factors up to the square root and none divided evenly, then number must be prime.

Append it to the list of primes.

break stops checking further factors (no need).

Example trace (num = 20)

• Start: primes = [2]

• number = 3 → factors checked: 2 (not divisible, 2 > √3) → add 3 → [2, 3]

• number = 4 → divisible by 2 → skip

• number = 5 → factors: 2 (not divisible), 3 (3 > √5) → add 5 → [2, 3, 5]

• number = 6 → divisible by 2 → skip

• number = 7 → factors: 2 (not divisible), 3 (3 > √7) → add 7 → [2, 3, 5, 7]

• number = 8 → divisible by 2 → skip

• number = 9 → divisible by 3 → skip

• number = 11 → factors: 2 (not divisible), 3 (not divisible), 5 (5 > √11) → add 11 → [2, 3, 5, 7, 11]

• … continues until 19.

Microsoft Copilot