Números primos

INTRODUÇÃO

Definição de número primo: Todo número primo é dividido por 1 e por ele mesmo.
Ex: 7, divisores são 1 e 7; 13, divisores são 1 e 13; 12 não é primo, pois temos os divisores 1, 2, 3, 4, 6, 12.
Objetivo
Mostrar o quanto podemos otimizar os algoritmos desde a definição até a melhor otimização, mostrando o quanto ele evolui a cada otimização.

Estrutura do trabalho
O trabalho está estruturado de forma que, gradativamente, se obtenha os conceitos necessários à compreensão da amplitude da otimização e sua importância.
Nesse trabalho será apresentada a evolução do algoritmo
1ª solução usando a definição

Leia C
S 0
Para i 2 até C-1 faça Se C resto i=0 então S S+i
Se S=0 então Imprima C “é primo”
Senão
Imprima C “não é primo”

Teste de Mesa
C S i imprima
9 0 2 3 4 5 6 7 8 9 9 não é primo

Conclusão
Facilmente percebemos que somente existem divisores de um número “n” qualquer entre 1 e (n/2), portanto todos os testes feitos entre (n/2) +1 e (n-1) são inúteis

2ª solução Otimizando (Metade)

Leia C
Para i 2 até inteiro (C/2) faça Se C resto i=0 então S S+i
Se S=0 então Imprima C “é primo”
Senão
Imprima C “não é primo” Teste de Mesa Teste de Mesa
C S i imprima C S i imprima
7 0 9 0 2 2 3 7 é primo 3 9 nào é primo

Conclusão
Facilmente percebemos que encontrado um divisor, o número candidato não será primo. A simples troca do para pelo enquanto resolve a questão.

3ª solução – enquanto

Leia C
S 0 i 2
Enquanto