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:

  1. Start with the candidate divisor \(d = 2\).

  2. If \(d\) divides \(n\), record \(d\) and replace \(n\) with \(n / d\). Otherwise, increase \(d\) by \(1\).

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

  1. If \(n = 1\), there are no prime factors. In this case, return an empty list [].

  2. Otherwise, search for the smallest integer \(d \ge 2\) with \(d^2 \le n\) that divides \(n\).

  3. If such a \(d\) exists, the prime factors of \(n\) are \(d\) followed by the prime factors of \(n / d\).

  4. 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\):

  1. Initialize a set of candidates \(C = \{2, 3, \ldots, N\}\).

  2. For \(p = 2, 3, 4, \ldots\), if \(p\in C\), remove its multiples \(p^2, p^2 + p, p^2 + 2p, \ldots\) from \(C\).

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