Como verificar se um número é primo em Python

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

Se você já fez testes de codificação, já deve ter se deparado com a questão de 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á:

• revisar os fundamentos 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 os fundamentos dos números primos.

Na teoria dos números, um número natural n disse-se estar melhor se tiver exatamente dois fatores : 1 e o próprio número (n ). Lembre-se da matemática da escola: um número eu é dito ser um fator do número n E se eu divide n uniformemente. ✅

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

Da tabela acima, podemos escrever o seguinte:

• 2 é o menor número primo.
• 1 é um fator de todo número.
• cada 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ê vai de 2 para n – 1, você deve não ser capaz de encontrar um fator não trivial que divida n sem deixar resto.

Algoritmo O(n) 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 range() objeto em Python.

Em Python, range(start, stop, step) retorna um objeto de intervalo. Você pode então iterar sobre o objeto range para obter uma sequência de start todo o caminho até stop -1 em passos 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 laço.

Aqui está o que gostaríamos de fazer:

• Se você encontrar um número que divide n uniformemente sem resto, você pode concluir imediatamente que o número não é primo.

• Se você percorreu todo o intervalo de números de 2 todo o caminho 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 ir em frente e definir a função is_prime() do seguinte modo.

  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() leva em um inteiro positivo n como o argumento.
• Se você encontrar um fator no intervalo especificado de (2, n-1), a função retornará False– já que o número não é primo.
• E ele 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.

Bem, podemos ver que o único fator de n isso é maior que n/2 é n em si.

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 verificar a saída por meio de algumas chamadas de função.

  is_prime(9)
# False

is_prime(11)
# True

Mesmo que pareça 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 Sobre) complexidade do tempo de execução: proporcional ao valor de n ou linear em n.

Podemos fazer melhor? Sim, nós podemos!

▶️ Prossiga para a próxima seção para determinar como melhorar a complexidade de tempo para testes 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 de tal modo 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.

Além disso, observe que √18 é aproximadamente 4,24.

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

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

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

▶️ Observe 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 eb > 6 vale.

Resumindo, temos o seguinte:

• cada número n pode ser escrito como n = axb
• Se n é um perfeito quadrado 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 otimizar a função para verificar 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 interno do Python e usar math.sqrt() função.
• Como n pode não ser um quadrado perfeito, teremos que transformá-lo em um número inteiro. Usar int(var) lançar var em um int.
• Para garantir que estamos verificando até √n, adicionamos um mais um como range() função 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 Notebook Jupyter ambiente 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 traçar 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 pandas DataFrame .
• Em seguida, plotamos usando lineplot de seaborn() função.

No gráfico abaixo, vemos que √n é significativamente menor que n.

Vamos agora aumentar o intervalo para até 2.000 e repetir as mesmas etapas 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)

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) levará cerca de 2.000 passos, o algoritmo O(√n) pode ajudar a chegar à resposta em apenas 49 passos.✅

Conclusão

⏳ E é hora de um rápido resumo.

• 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 somente 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 somente 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 em operações de string — onde você aprenderá a verificar se strings são palíndromos, anagramas e muito mais.

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