Prime Numbers¶
An integer \(p > 1\) is prime if its only positive divisors are \(1\) and \(p\). An integer \(n > 1\) that is not prime is composite, meaning that \(d \mid n\) for some \(d\) with \(1 < d < n\). For example, \(2\), \(3\), \(5\), \(7\), and \(11\) are prime, while \(12 = 3 \cdot 4\) is composite. The number \(1\) is neither prime nor composite.
The Fundamental Theorem¶
Prime numbers can be thought of as the “building blocks” for all integers due to the following result.
Theorem (The Fundamental Theorem of Arithmetic). Any integer \(n > 1\) has a factorization into primes, written
\[n = p_1 p_2 \cdots p_r\](for some \(r\in\mathbb{N})\) with \(p_1\le p_2 \le \cdots \le p_r\), and this factorization is unique.
For example,
and no other collection of primes multiplies to \(84\). Prime factorizations are easy to define but hard to compute for large numbers, and some cryptographic systems rely on that difficulty to keep data secure.
Testing for Primality¶
One way to decide whether a given positive integer \(n\in\mathbb{N}\) is prime is to search for a divisor of \(n\). Other than \(n\), the largest possible divisor for \(n\) is \(\sqrt{n}\), since if \(n = ab\) with \(1 < a \le b\), then \(a^2 \le ab = n\). In other words, every composite \(n\) has a divisor \(d > 1\) with \(d^2 \le n\).
Therefore, to test whether \(n > 1\) is prime, check the candidates \(d = 2, 3, 4, \ldots\) in order. If some \(d\) divides \(n\), then \(n\) is composite; if \(d^2 > n\) before any candidate divides \(n\), then \(n\) is prime.
For \(n = 91\), \(2\), \(3\), \(4\), \(5\), and \(6\) do not divide \(91\), but \(7\) does (\(91 = 7 \cdot 13\)), so \(91\) is composite. No further candidates need to be checked once a single divisor has been found.
For \(n = 97\), none of \(2, 3, \ldots, 9\) divides \(97\), and \(10^2 = 100 > 97\), so \(97\) is prime. Only \(8\) candidates need to be checked.
In Python, recall that \(d \mid n\) if and only if the remainder n % d equals zero.
print(17 % 3) # Nonzero, so 3 does not divide 17.
print(291 % 3) # Zero, so 3 divides 291.
2
0
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