The **Prime numbers** and the **composed numbers** are two types of **natural numbers**. That is, they are positive integers that can be used to count the elements of a certain set (1, 2, 3, 4, 5, … ).

Prime numbers only have 1 and itself as a divisor, so they only have 2 divisors, unlike composite numbers that have more than 2 divisors.

Next we are going to define more exactly what a prime number is and what a composite number is, we will see some examples and properties, and we will learn to distinguish whether a number is prime or composite.

## Prime number definition and examples

A **Prime number** is defined as a natural number greater than 1 that cannot be obtained as a product of two other natural numbers, only as a multiple of itself and 1.

In other words, a prime number is a natural number greater than 1 that **it only has two dividers**: the number itself and 1. A prime number has exactly those two divisors, no more and no less.

For example, the number 2 is a prime number because it is only divisible by 2 (the number itself) and by 1, and therefore can only be obtained by multiplying 2 x 1. There are no smaller natural numbers whose multiple is equal to two.

On the other hand, the number 4 is not prime, since it is divisible by 4, by 2 and by 1, and can be obtained by multiplying 2 × 2, in addition to 4 × 1.

Natural numbers that are not primes are called composite numbers, and all of them have more than two divisors: the number itself, 1, and at least one other natural number.

The **first 25 prime numbers** are all less than 100 and form the numerical sequence known as A000040 of the OESIS (On-Line Encyclopedia of Integer Sequences):

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

exist **infinite prime numbers**something that has already shown **Euclid** 300 years BC. The largest known prime number, as of January 2020, has almost 25 million digits.

### The number 1 is not considered prime or composite

It is very important to be clear that **the number 1 is not considered a prime number**since it only has one divisor: itself.

**It is also not considered a composite number.**since it cannot be broken down into the product of other natural numbers, only as a multiple of itself:

1 × 1 = 1

For the same reasons, the **zero** it is also not considered a prime or composite number.

### 2 is the only even prime number.

The number **two** it's a **even number** and it is a **Prime number**, since it only has two divisors. Above two, there is no even number that is also a prime number, since all of them are divisible, at least, by themselves, by 2 and by 1.

In other words, **all prime numbers other than 2 are odd numbers**.

Because of this feature, many ancient Greek mathematicians defined prime numbers as a subset of odd numbers and did not even consider the number 2 to be a prime number.

## Composite number definition and examples

All natural numbers are divisible, at least, by itself and 1. As we saw before, if a natural number only has these two divisors, it is a prime number. But if you have some other divisor then it is a **compound number**.

A composite number is defined as a natural number that has **more than two dividers**so it can be obtained as a product or multiple of two smaller natural numbers.

For example, the number 15 is a composite number. It can be divided by itself and by 1, and also by 3 and by 5. Therefore, it has 4 divisors: 1, 3, 5, and 15. Also, it can be obtained as a product of 3 × 5.

Another example would be the number 20, since it is divisible by 20, by 1, and also by 2, 4, 5 and 10. It can be obtained from the products 2 × 10 and 5 × 4.

## Most notable differences

As a summary of the differences between prime numbers and composite numbers, we can cite the following aspects:

- Both prime numbers and composite numbers are
**natural numbers**. - All prime and composite numbers are
**greater than 1**, since the number 1 is considered neither prime nor composite. Neither is zero. - All prime and composite numbers are divisible
**between themselves and between 1**. Composite numbers, moreover, are divisible by some other natural number. - A
**Prime number**has exactly**two dividers**: own number and 1. - A
**compound number**always has**more than two dividers**at least 3: the number itself, 1 and at least one other natural number. - A
**Prime number**can only be expressed as the product of**himself multiplied by 1**. - A
**compound number**can be expressed as a product of itself times 1, and at least as**product of another smaller natural number**. - The
**number 2**is he**unique prime number**which is also a**even number**. All other prime numbers are odd. - Among the composite numbers there are even and odd.
- There are infinitely many prime numbers and infinitely many composite numbers.

## How to tell if a number is prime or composite

There is no formula, or at least it is not known, with which one can **find out if a number is prime or composite**Therefore, various techniques are used.

One of the most used is a **essay test** which consists in beginning to divide the number ** n between 2, 3, etc.**until one of the

**divisions be exact**or until the

**quotient is less than divisor**.

If any division is exact, then it is a composite number, otherwise it is a prime number.

Instead of doing all the divisions starting from 2, it can be done only between the prime numbers (2, 3, 5, 7, 11, 13, …). The result will be the same.

This technique is very **slow and tedious**and the larger the number, the slower it will be to determine whether a number is prime or composite.

There are numerous **algorithms** much faster, like the Miller-Rabin primality test, which is fast but can give errors, or the AKS primality test, which has no errors but is still too slow.

### Example: Is 115 prime?

We begin to divide 115 by 2, 3, ….

- 115/2 = 57.5
- 115/3 = 38.33
- 115/5 = 23 → Exact division.

Here we stop, because the division by 5 is an exact division. That is, 115 is divisible by 5, so **115 is a composite number**.

### Example: Is 127 prime?

- 127/2 = 63.5
- 127/3 = 42.33
- 127/5 = 25.4
- 127/7 = 18.14
- 127/11 = 11.54
- 127/13 = 9.76 → the quotient (9.76) is less than the divisor (13)

Here we stop. All divisions are inexact, so **127 is a prime number**.