Prime numbers

Prime numbersThey are all natural numbers greater than one that are only divisible by themselves and by unity; 2 is a Prime number. The 1 is not because it has a single divisor, itself.

We can make use of an algorithm to find any prime number, for example, those between 1 and 1000; This is known as the Eratosthenes sieve, in honor of its inventor, the Greek mathematician and astronomer Eratosthenes (276 BC - 194 BC).

Definition

A Prime number is all that natural number greater than one that has the property of having only two divisors: the same number and the unit (1). For example, 2 is a prime number.

How to determine if a number is prime?

A natural number n will be a prime number if it meets the following three conditions:

  1. n> 1, that is, the number is greater than one.
  2. When dividing the number by itself, the result is 1.
  3. By dividing it by unity, the result is itself.

Example 1: 2 is a prime number because it meets all three conditions.

  • It is greater than one, 2> 1.
  • When we divide it by itself, the result is 1:

2/2 = 1

  • When we divide it by unity, the result is 2:

2/1 = 2

Example 2: 2437 is a prime number because it meets all three conditions.

  • It is greater than one, 2437> 1.
  • When we divide it by itself, the result is 1:

2437/2437 = 1

  • When we divide it by unity, the result is 2437:

2437/1 = 2437

The sieve of Eratosthenes

It is an algorithm that allows finding all prime numbers less than a given natural number n. To do this, we follow the following procedure:

  1. We create a table with the natural numbers between 2 and n.
  2. We remove all multiples of 2 from the table.
  3. We take the first number after 2 that was not removed (3) and remove its multiples from the table, and so successively.
  4. The process ends when the square of the largest number confirmed as prime is less than the final number of the board.  The numbers that remain in the table will be the cousins.

Example: Determine by the Eratosthenes sieve the prime numbers less than 30.

  1. We make a table with the natural numbers between and.

sieve of Eratosthenes

  1. We cross out all multiples of the table, that is, we eliminate all even numbers, starting with (since they have more than two divisors).

sieve of Eratosthenes

  1. Like, we cross out all the multiples of, that is, we remove the numbers in, starting with (since they have more than two divisors).

sieve of Eratosthenes

  1. Now, like, we cross out all the multiples of, that is, we remove the numbers in, starting with (since they have more than two divisors).

sieve of Eratosthenes

Like 7> 30, the algorithm ends and the remaining numbers are prime.

Prime numbers from 1 to 1000

Cousins table