Sieve of Eratosthenes 
Prime numbers
Consider the following problem:
The sentence "up to the order of factors" means that the order of factors does not matter. For example, \(2 \times 3\) and \(3 \times 2\) count as a unique way of writing \(6\) as a two-factor product.
For the number \(12\) we have three distinct ways: \(12 = 1 \times 12\) or \(12 = 2 \times 6\) or \(12 = 3 \times 4\). Therefore, the number \(12\) is not an answer to the problem. But for \(13\) we have only one way: \(13 = 1 \times 13\).
The numbers which, like \(13\), satisfy the following two conditions:
- can be written as a product of two factors only in one way (up to the order of the factors);
- the factors used in this (unique) decomposition are different;
are called prime numbers.
For instance, \(1\) is not prime because, although it satisfies the first condition
(as the only way to write \(1\) as a two-factor product is \(1=1 \times 1\)),
it does not satisfy the secound, since the factors of this (unique) decomposition
are equal. And, for example, \(4\) is also not prime because it does not satisfy
the first condition (as \(4\) can be written as a two-factor product in more
than one way: \(4=1 \times 4\) and \(4=2 \times 2\)).
On the other hand, \(2\), \(3\) and \(5\) are prime.
Numbers like \(12\), that can be written as a product of two factors in more than one way (up to the order of factors) are called composite numbers.
But why can \(12\) be written as a product of two factors in more than one way and \(13\) not? This is because the number \(13\) has only two divisors (\(1\) and \(13\)) whereas the number \(12\) has more than two divisors: \(2,3,4,6,12\).
A prime number is therefore a number that has exactly two (distinct) divisors.
Since \(1\) divides any number, one of the divisors of any prime number is necessarily the number \(1\). Moreover, any number is divisible by itself, so the other divisor of a prime number must be the number itself.
Thus, we can say that a prime number only admits as divisors \(1\) and the number itself.
A natural number is said to be composite when it has more than two (distinct) divisors, or equivalently, when it can be written as a product of two numbers smaller than itself.
We can thus conclude that any natural number different from 1 is either prime or composite.
The first prime numbers are \(2, 3, 5, 7, 11,...\).
| Number | Divisors | Is it prime? Is it composite? |
|---|---|---|
| \(1\) | \(1\) | It is neither prime nor composite |
| \(2\) | \(1,2\) | It is prime |
| \(3\) | \(1,3\) | It is prime |
| \(4\) | \(1,2,4\) | It is composite |
| \(5\) | \(1,5\) | It is prime |
| \(6\) | \(1,2,3,6\) | It is composite |
| \(7\) | \(1,7\) | It is prime |
| \(8\) | \(1,2,4,8\) | It is composite |
| \(9\) | \(1,3,9\) | It is composite |
| \(10\) | \(1,2,5,10\) | It is composite |
| \(11\) | \(1,11\) | It is prime |
Let us now recall question I and question II above.
Note that given a natural number greater than \(1\), its smallest divisor (different from \(1\)) is always a prime number (since any composite number is divisible by a number greater than \(1\) and less than itself). If a composite number is a divisor of another number, say \(n\), it will certainly not be its smallest divisor (distinct from \(1\)), since any divisor of this composite number will also be a divisor of \(n\).
