Assiste hoje mesmo às nossas aulas em vídeo com centenas de exercícios resolvidos. Aproveita e esclarece as tuas dúvidas todas!

Como verificar se um número é primo?

pequenas respostas para grandes perguntas

Um número primo só pode ter dois divisores, ele próprio e a unidade. É de salientar que qualquer número é divisível por ele próprio e pelo número um, a particularidade do número primo reside no facto de ele não ter mais nenhum divisor. Antes de analisar como é que isso pode ser testado usando uma linguagem de programação, pode experimentar verificar se um número é primo introduzindo esse número diretamente na seguinte caixa:

 

testar se um número é primo

Como testar se um número é primo utilizando programação?

A forma mais fácil de testar se um número é primo, consiste em dividir o número sucessivamente por todos os números entre dois e o próprio número menos um. Isto porque sabemos que qualquer número é divisível por um e por ele próprio. Se a divisão der resto zero, então foi encontrado um divisor do número. Assim que acharmos um divisor, podemos interromper o ciclo de repetição e afirmar que ele não é primo. Caso sejam feitas todas as divisões, sem conseguir encontrar um único divisor, então o número é primo:

NOTA

A linguagem de programação apresentada nos exemplos é o PHP. No entanto, o código pode ser facilmente adaptado para funcionar em C++ ou Java, uma vez que é muito semelhante. Se desejar poderá ver o código fonte desta página, para ver a sua adaptação em javascript.


function testarPrimo($numero){ 
	for ($i = 2; $i < $numero-1; $i++){ 
		if ($numero % $i == 0) 
			return false; 
	} 
	return true; 
}
	

O código apresentado anteriormente pode no entanto ser melhorado. Repare que se estivermos a testar se o número 97 é primo, a estrutura de repetição vai efetuar 95 divisões (divide por todos os números entre 2 e 96), mas isso é desnecessário. Nenhum número possui qualquer divisor maior que metade do seu valor. Assim sendo, o código pode ser melhorado, de forma a que o ciclo de repetição pare assim que alcançar metade do número que se pretende analisar:


function testarPrimo($numero){ 
	for ($i = 2; $i < $numero/2; $i++){ 
		if ($numero % $i == 0) 
			return false; 
	} 
	return true; 
}
	

Neste momento, se estivermos a testar se o número 97 é primo, a estrutura de repetição já só vai efetuar 47 divisões (divide por todos os números entre 2 e 48), mas ainda pode ser melhorado. Qualquer divisor do número maior que a sua raiz quadrada é múltiplo de um divisor menor já testado. Desta forma, o código pode ser corrigido, de maneira a que o ciclo de repetição pare assim que alcance a raiz quadrada do número que pretendemos testar:


function testarPrimo($numero){ 
	for ($i = 2; $i < sqrt($numero); $i++){ 
		if ($numero % $i == 0) 
			return false; 
	} 
	return true; 
}
	

Neste último exemplo, para testar se o número 97 é primo, apenas vão ser feitas 8 divisões (divide por todos os números entre 2 e 9). Este baixo número de divisões, já constitui uma melhoria significativa em relação à primeira versão do código. Ainda se poderiam introduzir novas funcionalidades no algoritmo, de forma a garantir que a sua execução seja ainda mais célere. Mas dado que isso implica conhecimentos mais avançados de matemática, fiquemos por aqui...

   Foi interessante? Então partilha!

Gostarias de referir este texto num trabalho escolar?

NUNES, Vitor F. R. "Como verificar se um número é primo?", matematica.pt. Disponível em: https://www.matematica.pt/faq/verificar-numero-primo.php, acedido em 23 de Julho de 2024.



Utiliza este espaço para comentários ou dúvidas

Neste local poderás colocar os teus comentários e as tuas dúvidas. Todas as mensagens que não estiverem diretamente relacionadas com este tema, ou que eventualmente contenham linguagem considerada imprópria serão removidas.

Foram feitos 4 comentários/dúvidas.
23 de Maio de 2020, 12h21

Mensagem de Roberto

Bom dia,
Parabéns pelo artigo! Sou um programador já com alguns anos de experiência e adorei a forma como explicam detalhadamente os pormenores do código. Apesar de ser relativamente fácil testar se um número é primo, a maior parte dos programadores que conheço, cria imensas linhas de código que não são eficientes quando estamos a testar números muito grandes. Esta é uma excelente forma de mostrar a utilidade dos conhecimentos matemáticos. Bom trabalho.

23 de Maio de 2020, 13h41

Mensagem de Vitor Nunes

Olá Roberto,
Concordo consigo. É relativamente fácil verificar se um número é primo, mas é complicado criar um algoritmo que faça isso de forma eficiente. Por acaso este artigo trata de duas áreas pelas quais tenho um especial apreço: matemática e programação. Espero que lhe tenha dado tanto prazer a ler como me deu a mim a escrever.

05 de Setembro de 2020, 20h37

Mensagem de Márcio

Esse algoritmo não leva em consideração de que o número 2 também é primo, uma vez que só é divisível por 1 e por ele mesmo.

06 de Setembro de 2020, 15h03

Mensagem de Vitor Nunes

Olá Márcio,
O algoritmo apresentado em linguagem PHP também funciona no caso do número 2. Esta página utiliza uma adaptação desse código para javascript, e se experimentar o número 2 no topo da página, recebe a indicação de que se trata de um número primo. Portanto está a funcionar corretamente.

Enviar Comentário/Dúvida




escrever carta

Consulta a nossa Lista de Perguntas para ficares a conhecer um pouco mais sobre os mais diversos temas relacionados com a matemática. Caso tenhas alguma pergunta (matemática) pertinente, cuja resposta não consigas encontrar facilmente, envia-nos um email através da página Contactar com essa dúvida. Teremos todo o gosto em responder. Na eventualidade de detetares algum erro nas nossas respostas, não hesites em avisar-nos!