Tweet

Números primos com Crivo de Eratóstenes em Fortran

Neste tutorial trago um algoritmo simples, escrito em Fortran, que permite encontrar os números primos de 1 até um valor n, informado pelo usuário durante a execução do programa, para isso usando o algoritmo clássico conhecido como Crivo de Eratóstenes.

Números primos são números naturais maiores que 1 que têm apenas dois divisores: 1 e eles mesmos. Em outras palavras, são números que não podem ser divididos por nenhum outro número além de 1 e deles mesmos sem resultar em um resto.

Exemplos de números primos incluem 2, 3, 5, 7 e 11.

A propriedade fundamental dos números primos é que não podem ser formados multiplicando dois números inteiros diferentes entre si. A compreensão dos números primos é crucial em matemática, e sua identificação desempenha um papel fundamental em áreas como criptografia e teoria dos números.

O Crivo de Eratóstenes é um algoritmo antigo e eficiente para encontrar todos os números primos até um determinado limite. Ele funciona marcando os múltiplos de cada número primo encontrado, eliminando números compostos e deixando apenas os números primos. O algoritmo realiza iterações até que todos os números até o limite desejado sejam verificados.

Trata-se de uma maneira bastante eficaz de encontrar rapidamente todos os números primos dentro de um intervalo específico.

De acordo com a tradição, o Crivo de Eratóstenes foi criado pelo matemático grego Eratóstenes de Cirene por volta de 240 a.C., sendo assim uma das técnicas mais antigas conhecidas para encontrar números primos.

Neste tutorial vamos implementar este algoritmo usando a linguagem de programação Fortran.

Funcionamento do Crivo de Eratóstenes

O algoritmo do Crivo de Eratóstenes funciona da seguinte maneira:

1. Inicialização:
   Começamos criando uma lista de números a partir de 2 até o valor limite desejado pelo usuário.
   Marcamos todos esses números como não riscados, indicando que inicialmente consideramos todos como primos.
2. Seleção do Próximo Número:
   Começamos com o primeiro número não riscado, que é o 2.
   Este número é então marcado como primo, já que é o menor número não riscado (e 2 é o primeiro número primo).
3. Eliminação dos Múltiplos:
   Agora vamos riscar todos os múltiplos do número primo que acabamos de encontrar, até chegar no valor limite.
   No caso, riscamos todos os múltiplos de 2 (4, 6, 8, 10, 12, …).
4. Seleção do Próximo Número Não Riscado:
   Após riscar os múltiplos do número anterior, vamos nos mover para o próximo número não riscado na lista, que é o próximo número primo.
5. Repetição:
   Repetimos os passos 3 e 4 até que tenhamos marcado todos os números não riscados como primos ou não primos.

Ao final do processo, os números que permanecem não riscados são os números primos dentro do intervalo desejado. O Crivo de Eratóstenes é eficiente porque evita a verificação de múltiplos de números que já foram marcados como não primos, reduzindo significativamente o número de iterações necessárias.

Visualmente, o que o crivo de Eratóstenes equivale ao seguinte:

	0	1	2	3	4	5	6	7	8	9
0	❌ 1	✅ 2	✅ 3	❌ 4	✅ 5	❌ 6	✅ 7	❌ 8	❌ 9	❌ 10
1	✅ 11	❌ 12	✅ 13	❌ 14	❌ 15	❌ 16	✅ 17	❌ 18	✅ 19	❌ 20
2	❌ 21	❌ 22	✅ 23	❌ 24	❌ 25	❌ 26	❌ 27	❌ 28	✅ 29	❌ 30
3	✅ 31	❌ 32	❌ 33	❌ 34	❌ 35	❌ 36	✅ 37	❌ 38	❌ 39	❌ 40
4	✅ 41	❌ 42	✅ 43	❌ 44	❌ 45	❌ 46	✅ 47	❌ 48	❌ 49	❌ 50
5	❌ 51	❌ 52	✅ 53	❌ 54	❌ 55	❌ 56	❌ 57	❌ 58	✅ 59	❌ 60
6	✅ 61	❌ 62	❌ 63	❌ 64	❌ 65	❌ 66	✅ 67	❌ 68	❌ 69	❌ 70
7	✅ 71	❌ 72	✅ 73	❌ 74	❌ 75	❌ 76	❌ 77	❌ 78	✅ 79	❌ 80
8	❌ 81	❌ 82	✅ 83	❌ 84	❌ 85	❌ 86	❌ 87	❌ 88	✅ 89	❌ 90
9	❌ 91	❌ 92	❌ 93	❌ 94	❌ 95	❌ 96	✅ 97	❌ 98	❌ 99	❌ 100

Podemos ver que os números primos estão destacados (check verde), ao passo que os números múltiplos, que não são primos, são descartados (x vermelho).

Este algoritmo é bastante empregado em matemática computacional e é uma abordagem clássica para encontrar números primos.

Vejamos agora como implementar esse algoritmo usando uma linguagem de programação – no caso, o Fortran.

Código em Fortran

program CrivoDeEratostenes
implicit none

integer, parameter :: MAX_N = 1000000
integer :: n
logical :: e_primo(MAX_N)
integer :: i, j

! Inicializar o vetor de primos como verdadeiro
e_primo = .true.

! Solicitar ao usuário que insira o valor de 'n'
write(*,*) 'Digite um número inteiro positivo n:'
read(*,*) n

! Verificar se o valor de n está dentro dos limites permitidos para números primos
if (n <= 1 .or. n > MAX_N) then
    write(*,*) 'Valor de n fora dos limites permitidos.'
    stop
end if

! Algoritmo do Crivo de Eratóstenes
do i = 2, n
    if (e_primo(i)) then
        do j = 2*i, n, i
            e_primo(j) = .false.
        end do
    end if
end do

! Exibir os números primos encontrados
write(*,*) 'Números primos de 1 até', n, ':'
do i = 2, n
    if (e_primo(i)) then
        write(*,*) i
    end if
end do

end program CrivoDeEratostenes

Teste

Para testar, vamos pedir ao programa para retornar todos os números primos até o valor 500.000 (quinhentos mil!):

Resultado (truncado):

2
3
5
7
11
...
499943
499957
499969
499973
499979

Explicação do Código

E como exatamente funciona esse código? Vejamos uma explicação passo a passo:

1. Declaração de Variáveis – Começamos declarando algumas variáveis:

• MAX_N: Valor máximo permitido para n (limite superior para encontrar números primos).
• n: Número que será fornecido pelo usuário.
• e_primo: Um array lógico que indica se um número é primo (TRUE) ou não (FALSE).
• i e j: Índices para iteração.

2. Inicialização:

• e_primo = .TRUE.: Inicializa o vetor de primos como verdadeiro.

3. Entrada do Usuário:

• write(*,*) ‘Digite um número inteiro positivo n:’: Solicita ao usuário que insira um número inteiro positivo.
• read(*,*) n: Lê o valor inserido pelo usuário.

4. Verificação do Limite:
– if (n <= 1 .or. n > MAX_N) then: Verifica se o valor de n está dentro dos limites permitidos para números primos.
– write(*,*) ‘Valor de n fora dos limites permitidos.’: Exibe uma mensagem de erro se o valor de n estiver fora dos limites.
– stop: Encerra o programa.

5. Algoritmo do Crivo de Eratóstenes:
– A estrutura de repetição do i = 2, n itera sobre todos os números de 2 até n.
– if (e_primo(i)) then: Verifica se i é marcado como primo.
– A estrutura de repetição interna do j = 2*i, n, i marca todos os múltiplos de i como não primos, já que eles são divisíveis por i.

6. Saída dos Números Primos Encontrados:
– write(*,*) ‘Números primos de 1 até’, n, ‘:’: Exibe uma mensagem indicando que os números primos estão sendo mostrados.
– A segunda estrutura de repetição do i = 2, n itera sobre todos os números de 2 até n.
– if (e_primo(i)) then: Verifica se i é marcado como primo.
– write(*,*) i: Exibe o número primo.

Conclusão

Neste artigo vimos como empregar a técnica do Crivo de Eratóstenes para determinar números primos na linguagem de programação Fortran. Esse mesmo código pode ser adaptado para outras linguagens, como Python, C++, C# ou Rust, de acordo com sua necessidade.