Como verificar se um número é primo?

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:

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:

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...

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.

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!