Testing whether a number is prime

This lesson covers testing for a prime number in R, with the aim of understanding a basic mathematical algorithm built on a loop.

Whether a number is prime — divisible only by 1 and itself — can be settled by testing divisibility from 2 up to its square root. If nothing divides it, it is prime.

The sample code loops over the range 2:floor(sqrt(n)) and concludes the number is not prime the moment it finds an i where n %% i == 0. Checking only as far as the square root works because any larger divisor is necessarily paired with a smaller one.

A common early stumble is why the square root is enough. Testing every number below n also gives the right answer, but stopping at the square root removes a great deal of wasted work.

It is an important mathematical property that underlies cryptography, and there is a more advanced technique — the Sieve of Eratosthenes — for finding many primes efficiently at once.