Como verificar se um número é primo em Python

Publicados: 2022-05-02

Este tutorial ensinará como escrever um programa em Python para verificar se um número é primo ou não.

Se você já fez testes de codificação, já se deparou com a questão matemática no teste de primalidade ou para verificar se um número é primo. E nos próximos minutos, você aprenderá a encontrar a solução ideal para essa questão.

Neste tutorial, você irá:

  • reveja o básico dos números primos,
  • escrever código Python para verificar se um número é primo e
  • otimize-o ainda mais para obter um algoritmo de tempo de execução O(√n).

Por tudo isso e muito mais, vamos começar.

O que é um número primo?

Vamos começar revisando o básico dos números primos.

Na teoria dos números, um número natural n é dito primo se tiver exatamente dois fatores : 1 e o próprio número ( n ). Lembre-se de sua matemática da escola: um número i é considerado um fator do número n , se i dividir n uniformemente.

A tabela a seguir lista alguns números, todos os seus fatores e se eles são primos.

n Fatores é Prime?
1 1 Não
2 1, 2 Sim
3 1, 3 Sim
4 1, 2, 4 Não
7 1, 7 Sim
15 1, 3, 5, 15 Não

A partir da tabela acima, podemos escrever o seguinte:

  • 2 é o menor número primo.
  • 1 é um fator de cada número.
  • Todo número n é um fator de si mesmo.

Então 1 e n são fatores triviais para qualquer número n. E um número primo não deve ter outros fatores além desses dois.

Isso significa que, quando você for de 2 para n – 1, não poderá encontrar um fator não trivial que divida n sem deixar resto.

O(n) Algoritmo para verificar se um número é primo em Python

Nesta seção, vamos formalizar a abordagem acima em uma função Python.

Você pode percorrer todos os números de 2 a n – 1 usando o objeto range() em Python.

Em Python, range(start, stop, step) retorna um objeto range. Você pode então iterar sobre o objeto range para obter uma sequência desde o start até a stop -1 em etapas de step .

Como precisamos do conjunto de inteiros de 2 a n-1, podemos especificar range(2, n) e usá-lo em conjunto com for .

Aqui está o que gostaríamos de fazer:

  • Se você encontrar um número que divida n uniformemente sem deixar resto, poderá concluir imediatamente que o número não é primo.
  • Se você percorreu todo o intervalo de números de 2 até n – 1 sem encontrar um número que divida n uniformemente, então o número é primo.

Função Python para verificar o número primo

Usando o acima, podemos seguir em frente e definir a função is_prime() da seguinte forma.

 def is_prime(n): for i in range(2,n): if (n%i) == 0: return False return True

Vamos agora analisar a definição de função acima.

  • A função acima is_prime() recebe um inteiro positivo n como argumento.
  • Se você encontrar um fator no intervalo especificado de (2, n-1), a função retornará False — pois o número não é primo.
  • E retorna True se você percorrer todo o loop sem encontrar um fator.

Em seguida, vamos chamar a função com argumentos e verificar se a saída está correta.

 is_prime(2) # True is_prime(8) # False is_prime(9) # False is_prime(11) # True

Na saída acima, você vê que 2 e 11 são primos (a função retorna True ). E 8 e 9 não são primos (a função retorna False ).

Como otimizar a função Python is_prime()

Podemos fazer uma pequena otimização aqui. Observe a lista de fatores na tabela abaixo.

Número Fatores
6 1, 2, 3 , 6
10 1, 2, 5 , 10
18 1, 2, 3, 6, 9 , 18

Bem, podemos ver que o único fator de n que é maior que n/2 é o próprio n .

Portanto, isso significa que você não precisa fazer um loop até n – 1. Em vez disso, você pode executar o loop apenas até n/2.

Se você não encontrar um fator não trivial até n/2, também não poderá encontrar um além de n/2.

Agora vamos modificar a função is_prime() para verificar os fatores no intervalo (2, n/2)

 def is_prime(n): for i in range(2,int(n/2)): if (n%i) == 0: return False return True

Vamos em frente e verificar a saída por meio de algumas chamadas de função.

 is_prime(9) # False is_prime(11) # True

Embora possa parecer que otimizamos, esse algoritmo não é mais eficiente que o anterior em termos de complexidade de tempo de execução. Na verdade, ambos têm complexidade de tempo de execução O(n) : proporcional ao valor de n ou linear em n.

Podemos fazer melhor? Sim, nós podemos!

️ Vá para a próxima seção para determinar como melhorar a complexidade do tempo para o teste de números primos.

Algoritmo O(√n) para verificar o número primo em Python

Acontece que os fatores de um número ocorrem em pares.

Se a é um fator do número n , então também existe um fator b tal que axb = n , ou simplesmente, ab = n .

Vamos verificar isso através de um exemplo.

A tabela abaixo mostra os fatores do número 18 ocorrendo em pares. Você pode verificar o mesmo para mais alguns números, se quiser.

Observe também que √18 é aproximadamente 4,24.

E nos fatores que ocorrem em pares (a, b) , você pode ver que se a for menor que 4,24, então b é maior que 4,24 — neste exemplo, (2, 18) e (3, 6).

uma b
1 18
2 9
3 6
Fatores de 18 em pares

A figura abaixo mostra os fatores de 18 plotados na reta numérica.

fatores-on-number-line

Se o número n for um quadrado perfeito, você terá a = b = √n como um dos fatores.

️ Veja os fatores de 36 na tabela abaixo. Como 36 é um quadrado perfeito, a = b = 6 é um dos fatores. Para todos os outros pares de fatores (a, b), a < 6 e b > 6 são válidos.

uma b
1 36
2 18
3 12
4 9
6 6
Fatores de 36 em pares

Resumindo, temos o seguinte:

  • Todo número n pode ser escrito como n = axb
  • Se n é um quadrado perfeito, então a = b = √n .
  • E se a < b , então, a < √n e b > √n .
  • Caso contrário, se a > b , então a > √n e b < √n .

Portanto, em vez de percorrer todos os inteiros até n/2, você pode optar por executar até √n. E isso é muito mais eficiente do que nossa abordagem anterior.

Como modificar o algoritmo is_prime() para O(√n)

Vamos continuar otimizando a função para verificar os números primos em Python.

 import math def is_prime(n): for i in range(2,int(math.sqrt(n))+1): if (n%i) == 0: return False return True

Agora, vamos analisar a definição da função acima:

  • Para calcular a raiz quadrada de um número, vamos importar o módulo matemático embutido do Python e usar a função math.sqrt() .
  • Como n pode não ser um quadrado perfeito, teremos que convertê-lo em um inteiro. Use int(var) para converter var em um int .
  • Para ter certeza de que estamos realmente verificando até √n, adicionamos um mais um, pois a função range() exclui o ponto final do intervalo por padrão.

A célula de código abaixo verifica se nossa função is_prime() funciona corretamente.

 is_prime(8) # False is_prime(15) # False is_prime(23) # True

Na próxima seção, vamos criar alguns gráficos simples para entender O(n) e O(√n) visualmente.

Comparando O(n) e O(√n) Visualmente

️ Execute o seguinte trecho de código em um ambiente de notebook Jupyter de sua escolha.

 import numpy as np import seaborn as sns import pandas as pd n = 20 x = np.arange(n) y1 = np.sqrt(x) y2 = x df = pd.DataFrame({"O(√n)":y1,"O(n)":y2}) sns.set_theme() sns.lineplot(data = df)

O trecho acima mostra como você pode plotar as curvas para n e √n para um intervalo de valores.

  • Usamos a função NumPy arange() para criar uma matriz de números.
  • E então, coletamos os valores de n e √n até, mas não incluindo 20, em um DataFrame pandas.
  • Em seguida, plotamos usando a função lineplot() do seaborn.

A partir do gráfico abaixo, vemos que √n é significativamente menor que n.

python de verificação de número primo

Vamos agora aumentar o intervalo para até 2000 e repetir os mesmos passos acima.

 import numpy as np import seaborn as sns import pandas as pd n = 2000 x = np.arange(n) y1 = np.sqrt(x) y2 = x df = pd.DataFrame({"O(√n)":y1,"O(n)":y2}) sns.set_theme() sns.lineplot(data = df) 
python de verificação de número primo

A partir do gráfico acima, você pode inferir que o algoritmo O(√n) é significativamente mais rápido quando você está testando se um número grande é primo.

Aqui está um exemplo rápido: 2377 é um número primo – verifique isso!

Enquanto a abordagem O(n) terá a ordem de 2.000 passos, o algoritmo O(√n) pode ajudar a chegar à resposta em apenas 49 passos.

Conclusão

E é hora de um resumo rápido.

  • Para verificar se um número é primo, a abordagem ingênua é percorrer todos os números no intervalo (2, n-1). Se você não encontrar um fator que divida n, então n é primo.
  • Como o único fator de n maior que n/2 é o próprio n, você pode optar por executar apenas até n/2.
  • Ambas as abordagens acima têm uma complexidade de tempo de O(n).
  • Como os fatores de um número ocorrem em pares, você pode executar apenas até √n. Este algoritmo é muito mais rápido que O(n). E o ganho é apreciável ao verificar se um número grande é primo ou não.

Espero que você entenda como verificar se um número é primo em Python. Como próximo passo, você pode conferir nosso tutorial sobre programas Python sobre operações com strings - onde você aprenderá a verificar se strings são palíndromos, anagramas e muito mais.

Vejo todos vocês em outro tutorial. Até lá, boa codificação!