Deste modo, vamos para um segundo exemplo de algoritmo que deve listar todos os números naturais primos até um n qualquer. Antes de prosseguir, procure pensar em: como você resolveria esse problema?

Pois bem, a primeira pessoa que se tem notícias que produziu tabelas de números primos foi uma pessoa chamada de Eratóstentes que viveu no terceiro século a.c (276 - 194) na Grécia antiga.

Eratóstenes criou um método, atualmente chamado de algoritmo, que possui a seguinte ideia: inicialmente ele escrevia um tabela com todos os números naturais de 1 à n, sendo que, neste caso, para simplificar o tamanho da tabela, 'n' estará valendo 120. Contudo, lembre-se que 'n' pode ser qualquer número natural maior que 1. Em seguida, escolhia o primeiro primo 'p' que, como já sabemos, é o número 2 e, consequentemente, eliminavam-se da lista todos os seus múltiplos. Observe que isso elimina metade dos números no intervalo de 1 à n escolhido. Depois escolhia o próximo número 'p' que ainda não tinha sido eliminado e, consequentemente, também eliminavam-se todos os seus múltiplos. Esse procedimento era executado até que p² ≤ n, e, consequentemente, a tabela contivesse apenas números primos. Observe que essa condição de parada é verdadeira pois não é preciso verificar todos os número no intervalo de 1 à 'n' uma vez que todos os números não primos são compostos e, consequentemente, podem ser reescritos em função de seus fatores primos. Mais tarde, esse algoritmo foi batizado como sendo o "crivo de Eratóstenes".

A partir desse procedimento podemos simplificar a descobertas de primos usando o lema : Se um número natural n > 1 não é divisível por nenhum primo p tal que p² ≤ n, então ele é primo. Este lema fornece um teste de primalidade, pois, para verificar se um dado número n é primo, basta verificar que não é divisível por nenhum p que não supere √n.

Este algoritmo inventado por Eratóstenes pode ser escrito também sob a forma de portugol, conforme demonstrado no exemplo abaixo:

	Declara vetor de reais valores[120];
	Declara inteiro maximo=120;
	Declara inteiro i;

	Inicio

	    para i de 0 a maximo faça
	        valores[ i ] ← i
	        i ← i + 1
	    fim_para

	    valores[0] ← 0
	    valores[1] ← 0

	    i ← 2

	    enquanto i^2 <= máximo faça
	        
	        se valores[ i ] != 0 então
	               eliminarPrimos( valores[ i ] )
	        fim_se
	      
	        i ← i + 1
	    
	    fim_enquanto

	Fim

	Função eliminarPrimos(inteiro i)

	    Declara inteiro j

	    j ← 2 * i;

	    enquanto j <= máximo faça
	        valores[ j ] ←0
	         j ← j + i;
	    fim_enquanto

	fim_eliminarPrimos
				
			

Observe que, tanto o algoritmo do exemplo anterior quanto este, são exemplos introdutórios da chamada programação estruturada, que consiste em organizar a ideia em termos de tipos/variáveis, estruturas de sequencia, decisão e repetição além de procedimentos/funções. Existe, portanto, uma separação muito bem definida entre dados (variáveis) e código (demais elementos).