Algoritmo Python Prime Checker
Verifique se um número é primo usando Python. Execute nosso algoritmo interativo para ver iteração matemática eficiente e avaliação de raiz.
Visão geral
Um número primo é um número inteiro positivo maior que 1 que não possui divisores positivos além de 1 e ele mesmo.
A maneira mais ineficiente de verificar um número primo é iterar até o próprio número. Uma otimização poderosa é verificar a divisibilidade apenas até a raiz quadrada do número.
Saída de código e execução
Algoritmo de verificação principal eficiente que demonstra a otimização O(sqrt(n)).
import math
def is_prime(n):
if n <= 1:
return False
if n == 2:
return True
if n % 2 == 0:
return False
max_divisor = math.isqrt(n)
for i in range(3, max_divisor + 1, 2):
if n % i == 0:
return False
return True
test_numbers = [2, 10, 17, 25, 97]
for num in test_numbers:
status = "Prime" if is_prime(num) else "Not Prime"
print(f"{num:2d} -> {status}") 2 -> Prime
10 -> Not Prime
17 -> Prime
25 -> Not Prime
97 -> PrimeImplementação passo a passo
- Algoritmos de criptografia e hash
- Matemática educacional e teoria da peneira
- Validação de back-end para chaves seguras
Perguntas frequentes
Por que verificar apenas até a raiz quadrada?
Se $n = a \times b$, então pelo menos um dos fatores ($a$ ou $b$) deve ser menor ou igual à raiz quadrada de $n$. Assim, verificar mais alto é redundante.
Tópicos Relacionados
Execute e entenda a sequência de Fibonacci em Python. Este exemplo de código interativo mostra abordagens iterativas e recursivas para gerar números de Fibonacci.
Algoritmos de classificação PythonExplore algoritmos de classificação python. Visualize a classificação por bolha e a classificação por mesclagem nativamente em um contexto IDE do navegador.