Números primos e compostos

Os números que possuem apenas dois divisores (ele próprio e 1) são chamados números primos.

Exemplos de números primos:

·         a) 2 é um número primo, pois D(2) = {1, 2} (lê-se: divisores de dois são o um e o 2)

·         b) 3 é um número primo, pois D(3) = {1, 3}

·         c) 5 é um número primo, pois D(5) = {1, 5}

·         d) 7 é um número primo, pois D(7) = {1, 7)

·         e) 11 é um número primo, pois D(11) = {1, 11}

O conjunto dos números primos é infinito.

P = {2, 3, 5, 7, 11,…}

Exemplos de números que não são primos:

·         a) 4 não é um número primo, pois D(4) = {1, 2, 4}

·         b) 6 não é um número primo, pois D(6) = {1, 2, 3, 6}

·         c) 8 não é um número primo, pois D(8) = {1, 2, 4, 8}

·         d) 9 não é um número primo, pois D(9) = {1, 3, 9}

·         e) 10 não é um número primo, pois D(10) = {1, 2, 5, 10}

Esses últimos exemplos são chamados de números compostos, pois possuem mais de dois divisores.

Por definição: 

·         O número 2 é o único número par que é primo.

·         O número 1 não é primo nem composto pois possui apenas 1 divisor.

O Crivo de Eratóstenes é um algoritmo e um método simples e prático para encontrar números primos até um certo valor limite. Segundo a tradição, foi criado pelo matemático grego Eratóstenes (c. 285-194 a.C.), o terceiro bibliotecário-chefe da biblioteca de Alexandria.

Para exemplificá-lo, vamos determinar a lista de números entre 1 e 30.

• Cria uma lista de todos os números inteiros de 2 até o valor limite: 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, e 30.

• Encontre o primeiro número da lista. Ele é um número primo, 2.

• Remova da lista todos os múltiplos do número primo encontrado, o 2, a azul na figura abaixo). No nosso exemplo, a lista fica: 2, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27 e 29.

• O próximo número da lista é primo. Repita o procedimento. No caso, o próximo número da lista é 3. Removendo seus múltiplos (a verde), a lista fica: 2, 3, 5, 7, 11, 13, 17, 19, 23, 25 e 29. O próximo número, 5, ( a vermelho) também é primo; a lista fica: 2, 3, 5, 7, 11, 13, 17, 19, 23 e 29. 7 é o último número a ser verificado (a amarelo). Assim, a lista encontrada contém somente números primos.

Em resumo: Um número natural é um número primo quando ele tem exatamente dois divisores: o número um e ele mesmo. 

Existem infinitos números primos, como demonstrado por Euclides por volta de 300 a.C.. 

A propriedade de ser um primo é chamada "primalidade", e a palavra "primo" também é utilizada como substantivo ou adjetivo. Como "dois" é o único número primo par, o termo "primo ímpar" refere-se a todo primo maior do que dois. 

Se um número inteiro tem módulo maior que um e não é primo, diz-se que é composto. Por convenção, os números 0, 1 e -1 não são considerados primos nem compostos. 

O conceito de número primo é muito importante na teoria dos números. Um dos resultados da teoria dos números é o Teorema Fundamental da Aritmética, que afirma que qualquer número natural diferente de 1 pode ser escrito de forma única (desconsiderando a ordem) como um produto de números primos (chamados fatores primos): este processo se chama decomposição em fatores primos (fatoração). 

Os 100 primeiros números primos positivos são: 

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, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541