# 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.