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 non-trivial divisor is a divisor strictly between \( 1 \) and \( n \). So, an integer greater than 1 is prime if it has no non-trivial 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 returns true if it is prime and false 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 speed-up to our primality test above.

exercise. Write an improved is_prime_naive? function that takes an integer input and returns true if it is prime and false 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.