prime numbers
An integer \( n \ge 2 \) is prime if its only positive divisors are \( 1 \) and \( n \) and composite otherwise.

The positive integer \( 1 \) is considered neither prime nor composite.

The divisors \( 1 \) and \( n \) are called the trivial divisors of \( n \). A nontrivial divisor is a divisor strictly between \( 1 \) and \( n \). So, an integer greater than 1 is prime if it has no nontrivial divisors and composite if it has a trivial divisor.
There are 25 primes up to 100, listed below.
PRIMES_UP_TO_100 = [
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,
]
We will use this list to test the primality testing methods we write later on.
def assert_correct_primality_using(method)
(100..1).each { x assert !send(method, x) }
primes, composites = (2..100).partition { x PRIMES_UP_TO_100.include? x }
primes.each { prime assert send(method, prime) }
composites.each { composite assert !send(method, composite) }
end
naive primality testing
exercise. Write an
is_prime_naive_v1?
function that takes an integer input and returnstrue
if it is prime andfalse
otherwise. It should only use only the definition.
def test_is_prime_naive_v1
assert_correct_primality_using :is_prime_naive_v1?
end
an improvement to naive primality testing
proposition 13. If an integer \( n \ge 2 \) is composite, then it has a divisor \( d \le \sqrt{n} \).
proof: We will prove this by contradiction. Suppose that a number \( n \) is composite and taht is has no divisor less than or equal to its square root. Since it is composite, it may be expressed as \( n = ab \) for some pair of integers \( a, b \). By hypothesis, both of these integers must be greater than \( \sqrt{n} \). Then \[ n = a \cdot b > \sqrt{n} \cdot \sqrt{n} = n, \] which is a contradiction since an integer cannot be greater than itself.
The proposition may also be restated in its contrapositive form.
proposition 13. If an integer \( n \ge 2 \) has no divisor less than or equal to its square root, then it is prime.
This rephrasing results in a substantial speedup to our primality test above.
exercise. Write an improved
is_prime_naive?
function that takes an integer input and returnstrue
if it is prime andfalse
otherwise. It should use both the definition and the proposition.
def test_is_prime_naive
assert_correct_primality_using :is_prime_naive?
end
This algorithm is still quite slow. Its time complexity grows as the square root of the input. We will develop some probabilistic methods that are very fast in a later section.