Testing whether a number is prime

This lesson covers testing for a prime number in Objective-C, 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 for (int i = 2; i * i <= n; i++) and concludes the number is not prime the moment it finds an i where n % i == 0. Note the BOOL return of YES or NO.

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.