Números primos usando Python

Escreva um programa para gerar uma lista de todos os números primos menores que 20.

Antes de começar, é importante notar o que é um número primo.

  1. Um número primo tem que ser um inteiro positivo
  2. Divisível por exatamente 2 inteiros (1 e ele mesmo)
  3. 1 não é um número primo

Embora existam muitas maneiras diferentes de resolver esse problema, aqui estão algumas abordagens diferentes.

Abordagem 1: For Loops

 # Inicialize uma lista 
primes = []
 for possiblePrime no intervalo (2, 21): 

# Assume que o número é primo até mostrar que não é.
isPrime = True
para num no intervalo (2, possiblePrime):
if possiblePrime% num == 0:
isPrime = False

se isPrime:
primes.append (possiblePrime)

Se você observar o loop for interno contido no retângulo vermelho abaixo, observe que assim que isPrime for False, será ineficiente continuar iterando. Seria mais eficiente sair do loop.

Abordagem 2: For Loops with Break

A abordagem 2 é mais eficiente que a abordagem 1 porque, assim que você descobrir que um determinado número não é um número primo, você pode sair do loop usando o break .

 # Inicialize uma lista 
primes = []
for possiblePrime no intervalo (2, 21):

# Assume que o número é primo até mostrar que não é.
isPrime = True
para num no intervalo (2, possiblePrime):
if possiblePrime% num == 0:
isPrime = False
pausa

se isPrime:
primes.append (possiblePrime)

A abordagem 2 é muito mais eficiente que a abordagem 1. Por exemplo, se você observar o caso quando possiblePrime = 15 , observe que há muito menos iteração na abordagem 2.

Abordagem 3: para Loop, Break e Raiz Quadrada

A abordagem 2 foi beneficiada por não fazer iterações desnecessárias no loop for interno. A abordagem 3 é semelhante, exceto a função de faixa interna. Observe que a função de faixa interna agora é range(2, int(possiblePrime ** 0.5) + 1) .

 # Inicialize uma lista 
primes = []
for possiblePrime no intervalo (2, 21):

# Assume que o número é primo até mostrar que não é.
isPrime = True
para num no intervalo (2, int (possiblePrime ** 0.5) + 1):
if possiblePrime% num == 0:
isPrime = False
pausa

se isPrime:
primes.append (possiblePrime)

Para explicar por que essa abordagem funciona, é importante observar algumas coisas. Um número composto é um número positivo maior que 1 que não é primo (que tem outros fatores além de 1 e ele próprio). Cada número composto tem um fator menor ou igual a sua raiz quadrada (prova aqui ). Por exemplo, na imagem dos fatores de 15 abaixo, observe que os fatores em vermelho são apenas os reversos dos fatores verdes. Em outras palavras, pela propriedade comutativa da multiplicação 3 x 5 = 5 x 3. Você só precisa incluir os pares verdes para ter certeza de que possui todos os fatores.

Fatores de 15

Comparação temporal de diferentes abordagens

Certos métodos para gerar números primos são mais eficientes. Para mostrar isso, vamos estudar o tempo a diferença de desempenho entre as abordagens gerando números primos até um determinado número.

Abordagem 1: For Loops

 def approach1 (givenNumber): 
 # Inicialize uma lista 
primes = []
para possiblePrime no intervalo (2, givenNumber + 1):
 # Assume que o número é primo até mostrar que não é. 
isPrime = True
para num no intervalo (2, possiblePrime):
if possiblePrime% num == 0:
isPrime = False
 se isPrime: 
primes.append (possiblePrime)
retorno (primos)

Abordagem 2: For Loops with Break

 def approach2 (givenNumber): 
 # Inicialize uma lista 
primes = []
para possiblePrime no intervalo (2, givenNumber + 1):
 # Assume que o número é primo até mostrar que não é. 
isPrime = True
para num no intervalo (2, possiblePrime):
if possiblePrime% num == 0:
isPrime = False
pausa
 se isPrime: 
primes.append (possiblePrime)

retorno (primos)

Abordagem 3: para Loop, Break e Raiz Quadrada

 abordagem def3 (givenNumber): 

# Inicialize uma lista
primes = []
para possiblePrime no intervalo (2, givenNumber + 1):
 # Assume que o número é primo até mostrar que não é. 
isPrime = True
para num no intervalo (2, int (possiblePrime ** 0.5) + 1):
if possiblePrime% num == 0:
isPrime = False
pausa
 se isPrime: 
primes.append (possiblePrime)

retorno (primos)

A diferença de desempenho pode ser medida usando a biblioteca timeit que permite a você cronometrar seu código Python. Neste caso, estamos medindo o tempo necessário para encontrar números primos até 500 para cada abordagem. O código abaixo executa o código para cada abordagem 10000 vezes e gera o tempo total em segundos.

 importar timeit 
 # Abordagem 1: tempo de execução 
print (timeit.timeit ('approach1 (500)', globals = globals (), número = 10000))
 # Abordagem 2: tempo de execução 
print (timeit.timeit ('approach2 (500)', globals = globals (), número = 10000))
 # Abordagem 3: tempo de execução 
print (timeit.timeit ('approach3 (500)', globals = globals (), número = 10000))

Claramente, o Approach 3 é o mais rápido.

Observações Finais

As três abordagens definitivamente não são as únicas maneiras de calcular números primos, mas esperamos que as várias maneiras de identificar números primos ajudem você. Os números primos são importantes na teoria dos números e nos métodos criptográficos, como o algoritmo rsa. Como sempre, o código no post também está disponível no meu github ( código de aproximação , comparação de tempo ). Se você tiver dúvidas ou pensamentos sobre o tutorial, fique à vontade para entrar nos comentários abaixo ou no Twitter .

Deixe uma resposta

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *