A prime number is any positive integer that can only be divided by 1 and itself. A number that is not prime is said to be composite.

Our computer will only be able to determine if $m$ is divisible by $n$ via Algorithm 1.A.

Problem 2.A: Determine if $n$ is prime

Given a positive integer $n$, we would like to determine if $n$ is prime. The following is an algorithm for determining if an integer is prime:

Algorithm 2.A(a)

Try dividing $n$ by every integer between $2$ and $n - 1$ and if any of these result in a remainder that is not zero, we know the number is not prime. If the remainder is non-zero for all integers from $2$ to $n - 1$, then $n$ is prime.

For this test, we have only two requirement of the person implementing this algorithm:

• the person must be able to add (to get from $2$ to $n - 1$), and
• the person must be able to find the remainder when calculating $n \div m$.

Thus, we know that $17$ is prime because:

• $17 = 2 \times 8 + 1$
• $17 = 3 \times 5 + 2$
• $17 = 4 \times 4 + 1$
• $17 = 5 \times 3 + 2$
• $17 = 6 \times 2 + 5$
• $17 = 7 \times 2 + 3$
• $17 = 8 \times 2 + 1$
• $17 = 9 \times 1 + 8$
• $17 = 10 \times 1 + 7$
• $17 = 11 \times 1 + 6$
• $17 = 12 \times 1 + 5$
• $17 = 13 \times 1 + 4$
• $17 = 14 \times 1 + 3$
• $17 = 15 \times 1 + 2$
• $17 = 16 \times 1 + 1$

Now, notice that all of the numbers $m \ge 5$ have a quotient less than the number itself. Thus, if we have already tested all numbers less than $5$, there is no point in testing numbers greater than or equal to $5$.

More generally, this should make you realize we only need to test numbers up to and including the square root of the integer because if $m_1 m_2 = n$ and $m_2 \ge \sqrt{n}$, then $m_1 \le \sqrt{n}$, and so if we already tested $m_1$, there is no need to test $m_2$.

Algorithm 2.A(b)

Try dividing $n$ by every integer between $2$ and $\sqrt{n}$ and if any of these result in a remainder that is not zero, we know the number is not prime. If the remainder is non-zero for all integers from $2$ to $\sqrt{n}$, then $n$ is prime.

Now, our computer cannot calculate the square root of an integer; instead, the computer can determine if $m^2 > n$, in which case $m > \sqrt{n}$.

For example, to determine that $257$ is prime, we only need to test $2$ through $16$ (as $17^2 = 289$) to determine if $257$ is prime:

• $257 = 2 \times 128 + 1$
• $257 = 3 \times 85 + 2$
• $257 = 4 \times 64 + 1$
• $257 = 5 \times 51 + 2$
• $257 = 6 \times 42 + 5$
• $257 = 7 \times 36 + 5$
• $257 = 8 \times 32 + 1$
• $257 = 9 \times 28 + 5$
• $257 = 10 \times 25 + 7$
• $257 = 11 \times 23 + 4$
• $257 = 12 \times 21 + 5$
• $257 = 13 \times 19 + 10$
• $257 = 14 \times 18 + 5$
• $257 = 15 \times 17 + 2$
• $257 = 16 \times 16 + 1$

Now, suppose that $6 \le \sqrt{n}$ and we determined that $n = 6m$. If this is true, then $n = 2(3m)$, so if $n$ is divisible by $6$, then $n$ is also divisible by $2$. As a consequence, if $n$ is not divisible by any of the prime divisors of a composite number (all of which are smaller than the composite), then $n$ is not divisible by that composite number, either.

From this, we may conclude that we really only have to test all prime numbers between $2$ and $\sqrt{n}$, inclusive.

Thus, to determine if $2221$ is prime, we need only test:

• $2221 = 2 \times 1110 + 1$
• $2221 = 3 \times 740 + 1$
• $2221 = 5 \times 444 + 1$
• $2221 = 7 \times 317 + 2$
• $2221 = 11 \times 201 + 10$
• $2221 = 13 \times 170 + 11$
• $2221 = 17 \times 130 + 11$
• $2221 = 19 \times 116 + 17$
• $2221 = 23 \times 96 + 13$
• $2221 = 29 \times 76 + 17$
• $2221 = 31 \times 71 + 20$
• $2221 = 37 \times 60 + 1$
• $2221 = 41 \times 54 + 7$
• $2221 = 43 \times 47 + 28$
• $2221 = 47 \times 41 + 12$

Thus, we could define the following algorithm:

Algorithm 2.A(c)

For each integer $m$ between $2$ and $\sqrt{n}$, if $m$ is prime, then try dividing $n$ by $m$ and if this results in a remainder that is not zero, we know the number $n$ is not prime. If the remainder is non-zero for all prime numbers from $2$ to $\sqrt{n}$, then $n$ is prime.

Our computer currently does not have have a list of all prime numbers between $2$ and $\sqrt{n}$, so for this algorithm, the computer would have to use Algorithm 1.A to test each integer for primality.

If we had a list of all prime numbers up to $\sqrt{n}$, we could rewrite this as

Algorithm 2.A

For each prime number $m$ between $2$ and $\sqrt{n}$, if dividing $n$ by $m$ and results in a remainder that is not zero, we know the number $n$ is not prime. If the remainder is non-zero for all prime numbers from $2$ to $\sqrt{n}$, then $n$ is prime.

For this algorithm to be efficient, we must find all prime numbers between $2$ and $\sqrt{n}$. We will now pose another problem.

Problem 2.B Find all prime numbers less than or equal to n

The most obvious algorithm, given what we have already seen, is as follows:

Algorithm 2.B(a)

Starting with the list of known primes starting with $2$. Next, for each odd number $m$ starting with $3$, if $m$ is divisible by any known prime, then $m$ is composite; otherwise, add $m$ to our list of known prime numbers.

For example, to find all prime numbers between $2$ and $40$, we may proceed as follows:

• $3$ is not divisible by $2$, so $3$ is prime.
  Our known primes are $2, 3$.
• $5$ is not divisible by $2$ or $3$, so $5$ is prime.
  Our known primes are now $2, 3, 5$.
• $7$ is not divisible by $2$, $3$ or $5$, so $7$ is prime.
  Our known primes are now $2, 3, 5, 7$.
• $9$ is divisible by $3$; it is composite.
• $11$ is not divisible by $2$, $3$, $5$ or $7$, so $11$ is prime.
  Our known primes are now $2, 3, 5, 7, 11$.
• $13$ is not divisible by $2$, $3$, $5$, $7$ or $11$, so $13$ is prime.
  Our known primes are now $2, 3, 5, 7, 11, 13$.
• $15$ is divisible by $3$; it is composite.
• $17$ is not divisible by any known prime, so $17$ is prime.
  Our known primes are now $2, 3, 5, 7, 11, 13, 17$.
• $19$ is not divisible by any known prime, so $19$ is prime.
  Our known primes are now $2, 3, 5, 7, 11, 13, 17, 19$.
• $21$ is divisible by $3$; it is composite.
• $23$ is not divisible by any known prime, so $23$ is prime.
  Our known primes are now $2, 3, 5, 7, 11, 13, 17, 19, 23$.
• $25$ is divisible by $5$; it is composite.
• $27$ is divisible by $3$; it is composite.
• $29$ is not divisible by any known prime, so $29$ is prime.
  Our known primes are now $2, 3, 5, 7, 11, 13, 17, 19, 23, 29$.
• $31$ is not divisible by any known prime, so $31$ is prime.
  Our known primes are now $2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31$.
• $33$ is divisible by $3$; it is composite.
• $35$ is divisible by $5$; it is composite.
• $37$ is not divisible by any known prime, so $37$ is prime.
  Our known primes are now $2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37$.
• $39$ is divisible by $3$; it is composite.

Thus, all known primes less than or equal to $40$ are

$2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37$.

Thus, because $41^2 = 1681$, it follows that we could use this list of prime numbers to determine if any number less than $1681$ is prime.

For example, to determine that $1369$ is not prime, we would continue finding the remainder when calculating $1369 \div 2$, $1369 \div 3$, ..., and finally see that $1369 = 37 \times 37 + 0$, so $1369$ is not prime.

One may ask, however, is there a more efficient means of finding all prime numbers less than or equal to a given number? For this, we will look at the sieve of Eratosthenes.

The Sieve of Eratosthenes

The

	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40

The first number that is prime is $2$, so delete all multiples of $2$:

	2	3		5		7		9
11		13		15		17		19
21		23		25		27		29
31		33		35		37		39

The next number that is therefore prime is $3$, so eliminate all multiples of three:

	2	3		5		7
11		13				17		19
		23		25				29
31				35		37

The next number that is therefore prime is $5$, so eliminate all multiples of five:

	2	3		5		7
11		13				17		19
		23						29
31						37

The next number that is therefore prime is $7$, so eliminate all multiples of seven, but there are no more multiples of seven! If you check, no multiples of any of the remaining prime numbers exist in the table, so we are done: all prime numbers between $2$ and $40$ include

$2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37$

At this point, with a little thought, we can actually make this algorithm more efficient:

Algorithm 2.B: The Sieve of Eratosthenes

Starting with a table of all integers from $2$ to $n$, allow each to be flagged as either prime, composite or unknown. Start by flagging all as unknown, and iterate:
1. Let $m$ be the next unknown integer and flag it as prime.
2. If $m^2 > n$, we are done; all remaining unknown integers between $m$ and $n$ inclusive are prime.
Otherwise, for all multiples of $m$ starting with $m^2, (m + 1)m, (m + 2)m, \ldots$ until $(m + k)m > n$ as being composite, and then return to Step 1 and repeat.

This is actually a very efficient algorithm.

Analysis

Without further proof, although you are welcome to read about this elsewhere, to determine if a number approximately as large as ten thousand to be prime, we must find all prime numbers between two and $100$. This requires approximately $100 \ln(\ln( 100 )) \approx 153$ steps using Algorithm 2.B, and there are approximately $\frac{100}{\ln( 100 )} \approx 22$ prime numbers between two and $100$, so this will require approximately $22$ long divisions.

Similarly, to determine if a number approximately as large as one trillion to be prime, we must find all prime numbers between two and one million. This requires approximately $10^6 \ln(\ln( 10^6 )) \approx 2625792$ steps using Algorithm 2.B, and there are approximately $\frac{10^6}{\ln( 10^6 )} \approx 72382$ prime numbers between two and one million, so this will require approximately $72382$ long divisions. The only difficulty is that this will require a table with approximately one million entries.