Exercises¶
Problem 1
Write a function named is_prime() that accepts a positive integer \(n\).
Search for a divisor \(d\) of \(n\), starting from \(d = 2\) and stopping once \(d^2 > n\).
Return True if \(n\) is prime and False otherwise.
Hint: int(n**0.5) is the greatest integer that is less than or equal to \(\sqrt{n}\).
Test Cases
print(is_prime(1))
print(is_prime(2))
print(is_prime(97))
print(is_prime(100))
print(is_prime(215443))
False
True
True
False
True
Problem 2
Write a function named factor_brute() that accepts a positive integer \(n\).
Compute the prime factorization of \(n\) by trial division:
Start with the candidate divisor \(d = 2\).
If \(d\) divides \(n\), record \(d\) and replace \(n\) with \(n / d\). Otherwise, increase \(d\) by \(1\).
Repeat step 2 until \(d > n\).
Return a list of the recorded prime factors, with repetition, in increasing order.
Reminder: Floor division // keeps \(n / d\) an integer.
Test Cases
print(factor_brute(60))
print(factor_brute(97))
print(factor_brute(1024))
[2, 2, 3, 5]
[97]
[2, 2, 2, 2, 2, 2, 2, 2, 2, 2]
Problem 3
Write a function named factor_recursive() that accepts a positive integer \(n\).
Compute the prime factorization of \(n\) recursively:
If \(n = 1\), there are no prime factors. In this case, return an empty list
[].Otherwise, search for the smallest integer \(d \ge 2\) with \(d^2 \le n\) that divides \(n\).
If such a \(d\) exists, the prime factors of \(n\) are \(d\) followed by the prime factors of \(n / d\).
If no such \(d\) exists, then \(n\) is prime.
Return a list of the prime factors of \(n\), with repetition, in increasing order.
Hint: List addition performs concatenation; for example, [1, 2] + [3] evaluates to [1, 2, 3].
Test Cases
print(factor_recursive(60))
print(factor_recursive(97))
print(factor_recursive(1024))
[2, 2, 3, 5]
[97]
[2, 2, 2, 2, 2, 2, 2, 2, 2, 2]
Problem 4
Write a function named prime_sieve() that accepts a positive integer \(N\).
Use the sieve of Eratosthenes to find every prime less than or equal to \(N\):
Initialize a set of candidates \(C = \{2, 3, \ldots, N\}\).
For \(p = 2, 3, 4, \ldots\), if \(p\in C\), remove its multiples \(p^2, p^2 + p, p^2 + 2p, \ldots\) from \(C\).
Stop when \(p^2 > N\); the remaining candidates are all prime.
Return the list of resulting primes, sorted from least to greatest.
Hint 1: Store the candidates in a set, and remove numbers with the discard() method.
Hint 2: Convert the candidate set to a sorted list at the end with sorted().
Test Cases
print(prime_sieve(1))
print(prime_sieve(2))
print(prime_sieve(4))
print(prime_sieve(100))
[]
[2]
[2, 3]
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]