52

Atenção: Não estou procurando por pedaços de código prontos. Quero apenas que alguém me ajude a pensar em alguma forma de gerar esses 200.000 primos da forma mais eficiente possível, em Python.

Estou resolvendo a questão #61 do CodeAbbey, mas não estou conseguindo pensar em como gerar os primos que o exercício pede.

O enunciado, basicamente, considera que existe uma lista que contém todos os números primos do mundo, a começar pelo 2. Com base nessa lista, o enunciado dá uma série de índices (índices dessa lista), e o programa tem que retornar o primo que ocupa esse índice nessa lista imaginária.

Ex.:

Na lista [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ...], o índice 1 é 3; o 2 é 5, ...

O enunciado garante que a série de índices que ele vai fornecer aleatoriamente não possui nenhum índice superior a 200.000 (por isso 200.000 primos, no máximo)

Exemplo de input e output:

input data:
7 1 199999 4    # são os índices da lista imaginária

answer:
19 3 2750131 11    # são os primos dessa lista, correspondentes aos índices acima

No final do enunciado, o CodeAbbey avisa que existe uma forma de gerar o resultado em +/- 1 segundo.

Deixei o meu programa rodando por 10 minutos e não gerou resultado. Talvez um segundo seja muito pouco tempo, mas com certeza tem como resolver em... menos de 20 segundos?

Para tentar resolver, estou implantando o Sieve of Eratosthene (ou Crivo de Eratóstenes)

Segue meu código atual:

from math import sqrt

def primos(n, maxIndex):
    maiorCheck = int(sqrt(n))
    lista = []
    i, x, qtdPrimos = 0, 0, 0
    for m in range(2, n+1):
        lista.append(m)
    while x <= maiorCheck:
        x = lista[i]
        i += 1
        for numero in lista:
            if numero != x:
                if numero % x == 0:
                    lista[lista.index(numero)] = 0
        while 0 in lista:
            del lista[lista.index(0)]
        if len(lista) == maxIndex:
            x = maiorCheck + 1
    return lista

qtdPrimos = int(input('Entre com a quantidade de primos a serem impressos: ').strip())

indexes = input('Entre com os índices para os quais serão retornados primos: ').strip().split()
result = []

for n in range(len(indexes)):
    indexes[n] = int(indexes[n])

arrayPrimos = primos(2750131, max(indexes))

for m in range(len(indexes)):
    result.append(str(arrayPrimos[indexes[m]-1]))

print('\n--- R E S U L T A D O ---\n'+' '.join(result))
6
  • 3
    Boa pergunta. Eu mesmo consegui fazer em 12 segundos no console do Chrome, gostaria de saber como fazer mais rápido. Commented 23/08/2017 às 17:34
  • 2
    A pergunta é uma das mais bem feitas do site, o título nem tanto. Esse requisito de tempo é complicado.
    – Maniero
    Commented 23/08/2017 às 17:37
  • 1
    @bigown Melhorei o título, deixando o requisito de tempo menos rigoroso. Commented 23/08/2017 às 17:39
  • 1
    Maninho tenho um exemplo em Java que produz primos de forma bastante rápida talvez possa te ajudar link: github.com/HallefBruno/Estrutura-de-dados/blob/master/…
    – Bruno
    Commented 23/08/2017 às 17:47
  • 4
    Um dos problemas mais complexos que existe é gerar primos, o problema vai se agravando quanto mais números deseja. Tem algoritmos complexos que podem ir melhorando, eu nem vi seu código, mas não precisa verificar tudo. Eu nem optei pelas sacanagens que é não gerar os primos e sim fornecê-los :) Veja en.wikipedia.org/wiki/Sieve_of_Atkin
    – Maniero
    Commented 23/08/2017 às 18:03

8 Respostas 8

50
+100

Com o próprio Crivo de Eratóstenes eu consegui resultados bem satisfatórios. Vale lembrar que, como o crivo retorna a lista de todos os números primos menores que o valor de entrada, teremos que informar o maior valor primo que o programa aceitará. O enunciado fala que é garantido que não será solicitado um número após o 200.000°, então inicialmente devemos conhecer qual é este valor: 2.750.159.

Uma implementação bastante simples do crivo é:

def sieve_of_eratosthene(N):

    # Cria-se uma lista referente a todos os inteiros entre 0 e N:
    A = [True] * (N+1)

    # Define os números 0 e 1 como não primos:
    A[0] = A[1] = False

    # Percorra a lista até encontrar o primeiro número primo:
    for value, prime in enumerate(A):

        # O número é primo?
        if prime:

            # Retorna o número primo:
            yield value

            # Remova da lista todos os múltiplos do número encontrado:
            for i in range(value**2, N+1, value):
                A[i] = False

Assim, podemos obter todos os 200.000 primeiros números primos fazendo:

primes = list(sieve_of_eratosthene(2750159))

E gerar a saída da seguinte forma:

print("Saída:", [primes[i] for i in [7, 1, 199999, 4]]) # Saída: [19, 3, 2750159, 11]

Sendo [7, 1, 199999, 4] a entrada do programa.

Nota: o 199.999° número primo será 2.750.131, como esperado, apenas se o número 2 ocupar o índice 1. Considerando que a implementação define o índice 0 para o valor 2, o valor esperado na saída seria referente ao índice 199.998°.

Utilizando o módulo timeit para a medição do tempo, obtive um tempo médio, em 100 execuções, de 0.69539769177063s.

Veja funcionando no Ideone.

Uma breve explicação do código

A primeira linha da função, A = [True] * (N+1) cria uma lista de N+1 elementos, todos definidos como True, indicando inicialmente que todos os valores entre 0 e N são números primos. Logo após, é definido os valores 0 e 1 como False, indicando que estes não são números primos. E com um laço de repetição, é percorrido todos os outros valores e sempre que achar um valor primo, retorne-o e elimina da lista, definindo como False, todos os números que são múltiplos desse primo encontrado. Para uma melhor visualização, a lista A seria algo como:

A = [False, False, True, True, False, True, False, ...]

Indicando que 0 não é primo, 1 não é primo, 2 é primo, 3 é primo, 4 não é primo, 5 é primo, 6 não é primo, assim sucessivamente. O que a função enumerate faz é retornar um par de valores onde o primeiro representa o índice na lista e o segundo o valor propriamente dito. Assim, fazendo enumerate(A), seria retornado algo semelhante à:

[(0, False), (1, False), (2, True), (3, True), (4, False), (5, True), (6, False), ...]

E é por isso que no for existem dois valores. O primeiro valor retornado de enumerate é atribuído à value e o segundo à prime, assim, quando prime for verdadeiro, sabemos que value será um número primo.

for value, prime in enumerate(A):
    ...

Já o yield faz o papel do return, porém, para um gerador. Confesso que eu acabei complicando mais que o necessário neste código utilizando um gerador, pois visto que o gerador deverá ser convertido para uma lista, eu poderia gerá-la diretamente. O código ficaria assim:

def sieve_of_eratosthene(N):
    
    # Lista de números primos:
    numbers = []
 
    # Cria-se uma lista referente a todos os inteiros entre 0 e N:
    A = [True] * (N+1)
 
    # Define os números 0 e 1 como não primos:
    A[0] = A[1] = False
 
    # Percorra a lista até encontrar o primeiro número primo:
    for value, prime in enumerate(A):
 
        # O número é primo?
        if prime:
 
            # Retorna o número primo:
            numbers.append(value)
 
            # Remova da lista todos os múltiplos do número enontrado:
            for i in range(value**2, N+1, value):
                A[i] = False
                
    return numbers

Veja funcionando no Ideone.

Perceba que a principal diferença é que onde antes eu utilizada o yield, agora utilizei o append de uma lista.

Uma implementação extra

Assim como comentado pelo LINQ em sua resposta, o fato de ter que conhecer de antemão o n-ésimo valor primo pode ser considerado um limitante da solução. Uma alternativa prática é aplicar o conceito matemático apresentado no final desta resposta para calcular um valor primo próximo ao desejado. Sabendo que o n-ésimo número primo, Pn, é menor que n ln(n) + n ln(ln(n)), se calcularmos todos os valores primos até este valor temos certeza que teremos calculado o valor de Pn. Algo como:

def sieve_of_eratosthene(N):
    
    N = floor(N*log(N) + N*(log(log(N))))
    
    # Lista de números primos:
    numbers = []
 
    # Cria-se uma lista referente a todos os inteiros entre 0 e N:
    A = [True] * (N+1)
 
    # Define os números 0 e 1 como não primos:
    A[0] = A[1] = False
 
    # Percorra a lista até encontrar o primeiro número primo:
    for value, prime in enumerate(A):
 
        # O número é primo?
        if prime:
 
            # Retorna o número primo:
            numbers.append(value)
 
            # Remova da lista todos os múltiplos do número encontrado:
            for i in range(value**2, N+1, value):
                A[i] = False
                
    return numbers

Veja funcionando no Ideone.

Apenas com a adição da primeira linha, agora podemos chamar a função sieve_of_eratosthene(2e5) para obter os 200.000 primeiros números primos. Na verdade, obtém-se até mais, por isso o tempo de execução pode aumentar.


Possível alternativa

É provado matematicamente, se entendi bem, que o n-ésimo número primo, sendo n maior ou igual a 6, pertencerá ao conjunto de números definido por:

inserir a descrição da imagem aqui

Por exemplo, para n = 199999, é obtido o seguinte conjunto:

2741586 < P_n < 2941585

Que contém o valor esperado 2750159; porém, este não será o único número primo neste intervalo, então o desafio seguindo esta lógica seria identificar corretamente o valor dentro do intervalo.

13
  • Excelente! Muito bom! Agora foi muito rápido. Commented 24/08/2017 às 13:42
  • Mas eu não entendi um monte de coisas que você fez na função sieve_of_eratosthene... Pode me apontar os conceitos que você usou pra eu pesquisar? Sou novato ainda... Commented 24/08/2017 às 13:42
  • @santosmarco_ que conceitos seriam esses que não entendeu?
    – Woss
    Commented 24/08/2017 às 14:37
  • 2
    Estava pensando nessa pergunta ontem :), depois vou testar as propostas
    – Syzoth
    Commented 29/08/2017 às 21:45
  • 3
    Esta resposta é fantástica. Coloquei uma recompensa na pergunta para chamar a atenção e no final do prazo, darei os +100 para você. Commented 24/09/2018 às 19:05
18

Minha contribuição é uma implementação um tanto ingênua. Leva (na minha máquina) aproximadamente 71 segundos para gerar 200.000 primos. Apesar disso, é uma implementação básica, não usa nada de terceiros e é bem fácil de entender.

Nesta implementação, não é necessário saber de antemão qual é o n-ésimo número primo, ou seja, é possível criar uma lista com qualquer quantidade de números primos.

Note que não é uma adaptação do seu código, foi criado do zero. O algoritmo consiste em ir procurando de "forma bruta", checando todos os números ímpares.

O algoritmo se baseia na afirmação de que um número é composto (não-primo) se, se somente se, houver algum divisor primo menor ou igual a sua raiz quadrada.

from math import sqrt, ceil
import time

def checkPrime(num):
    if num % 2 == 0: return False
    i = 3
    while i <= ceil(sqrt(num)):
        if num % i == 0: 
            return False
        i += 2
    return True

def primes(q):
    primelist = [2]
    number = 3
    while len(primelist) < q:
        if(checkPrime(number)):
            primelist.append(number)        
        number += 2    
    return primelist

Versão 2

Este leva 24 segundos (na mesma máquina) pra gerar os 200.000 primos. A diferença deste pro outro é que, na checagem pra saber se um número é primo ou não, são usados apenas os números primos já conhecidos.

Isso porque, como eu disse acima, um número é composto (não-primo) quando tem algum divisor primo menor ou igual a sua raiz quadrada.

def checkPrime(num, baseList):    
    for p in baseList:
        if(p > ceil(sqrt(num))): break

        if num % p == 0:
            return False
    return True

def primes(q):
    primelist, number = [2], 3

    while len(primelist) < q:
        if checkPrime(number, primelist):
            primelist.append(number)
        number += 2
    return primelist

O uso seria assim:

def main():
    lista = primes(200000)
    print("Saída: ", [lista[i] for i in [199999, 1, 7]])

Saída: [2750159, 3, 19]

10
  • Este último a saída não está errada ? Para os índices 199999 e 7, segundo o link do enunciado...]
    – MagicHat
    Commented 24/08/2017 às 17:40
  • @MagicHat Só vai ser daquele jeito se começar a contar do 1
    – Jéf Bueno
    Commented 24/08/2017 às 17:42
  • "Eles estarão no alcance de 1 para 200000. ";)
    – MagicHat
    Commented 24/08/2017 às 17:43
  • @MagicHat É só diminuir 1 da entrada do usuário e ser feliz, não vejo o porquê disso invalidar a resposta. O principal ponto é como gerar os números em um tempo aceitável e não fazer todo o exercício para o AP
    – Jéf Bueno
    Commented 24/08/2017 às 17:44
  • Saquei, no caso sua resposta é legal tmb, por que como a do lacobus não é necessário saber o valor do último primo...
    – MagicHat
    Commented 24/08/2017 às 18:04
10

Cheguei atrasado na resposta. Porém, vou contribuir com uma implementação que é muito interessante e útil, porque ela NÃO PRECISA DE LIMITE.

Ela usa o algoritmo do 'crivo de Erastóthenes', porém de forma invertida, móvel, armazenando somente 1 múltiplo futuro de cada combinação de primos e liberando memória à medida que vai avançando, de forma que não é preciso definir de antemão qual o final do cálculo! E assim também não é preciso definir uma enorme lista na memória para ser marcada.

def eratosthenes():
    D = {}  # dicionario para armazenar os futuros primos
    q = 2   # primeiro inteiro a testar
    while True:
        if q not in D:
            yield q       # nao esta marcado entao eh primo
            D[q*q] = [q]  # armazena somente o primeiro multiplo 
                          # que ainda nao esta armazenado
        else:
            for p in D[q]:  # todos os nao-primos armazenados aqui precisam andar
                D.setdefault(p+q,[]).append(p)
            del D[q]        # libera memoria do que ja passou
        q += 1

Sendo assim, você pode chamar essa função e parar quando quiser, por exemplo

for p in eratosthenes():
    if p > 200000:
        break
    print(p)
2
  • Escrevendo na saída padrão demorou 1min22 segundos no meu WSL, jogando no /dev/null demorou 5.2s. A solução do Woss (imprimindo todos os números também) demorou 43s escrevendo na saída padrão, e 1.7s jogando no /dev/null. Fiz uma alteração para buscar apenas metade dos números na sua resposta (precisa passar por todos para fazer "andar" o crivo, mas não testo os pares, só os ímpares), os tempos foram 53s e 5.1s Commented 8/04/2020 às 18:54
  • Porém essa solução é infinita e a do Woss não é @JeffersonQuesado
    – nosklo
    Commented 9/04/2020 às 10:56
7

Código:

p = []

def gerar_primos():

    limite = 2750159 + 1

    primos = []
    nao_primo = set()

    for n in range( 2, limite ):

        if n in nao_primo:
            continue

        for f in range( n * 2, limite, n ):
            nao_primo.add( f )

        primos.append( n )

    return primos;


def primo(idx):

    global p

    if not p:
        p = gerar_primos();

    return p[ idx - 1 ]


print primo(7)
print primo(1)
print primo(199999)
print primo(4)

Saída:

$ time python primos.py 
17
2
2750131
7

real    0m1.963s
user    0m1.891s
sys 0m0.072s
0
2

Sei um pouco de Java e estou aprendendo Python. Fiz esse algoritmo e ele calcula todos os números ímpares de forma extremamente rápida. No meu notebook ele calcula e imprime todos os números primos de 0 a 1.000.000 em menos de 3 segundos. E de 0 a 4.000.000 faz em cerca de 17 segundos.

import time

num2 = int(input("Informe até qual número procurar: "))
inicio = time.time()
print("Esses são os número primos entre 0 e %i"%num2)
# lista com o primeiro número primo.
primos = [2,]
print(primos[0])

# só testa números impares
for x in range(3,num2+1,2):
num_divisoes = 0
    # pega o primeiro número e tenta dividi-lo pelos número primos menores que ele.
    for y in primos:
        # Quando o cociente for menor que o divisor para de testar números primos maiores.
        if x//y < y:
            break

        #se der para dividir o número por algum número primo já descoberto então ele não é primo.
        if x % y == 0:
            #marca que ele não é primo.
            num_divisoes = 1
            break

    # se não tiver nenhuma divisão adiciona o número na lista de primos.
    if num_divisoes == 0:
        primos.append(x)
        print(x)
        num_divisoes = 0

print("Existe %i números primos entre 0 e %i"%(len(primos),num2))
fim = time.time()
print("Executado em %.3f segundos"%(fim-inicio))

O que fez meu código ficar extremamente rápido foi essa parte:

# Quando o cociente for menor que o divisor para de testar números primos maiores.
if x//y < y:
   break

Sem esse trecho o número primo 999.983 faria cerca de 78.497 testes para verificar se ele é primo. Como esse código ele faz apenas 169 testes.

0

Todos os primos até 2.000.000 - leva tempo razoável; para 200.000 é rápido.

m = 200000 # para calcular primos até esse número m
# constrói a list comprehension excluindo os divisíveis pelos menores números primos
P = [2] + [3] + [5] + [x for x in range(7,m,2) if x % 3 != 0 and x % 5 != 0]
PL = len(P)
i = 15 # menor composto a excluir tem índice 15: é o 49
while i < PL:
    # Os divisíveis por 2, 3, e 5 já foram excluídos.
    # Começamos a excluir os divíveis de 7, cujo índice na list é 3
    j = 3 # P[3] = 7, menor primo para iniciar teste
    while i < PL and P[j] * P[j] <= P[i]:
    if P[i] % P[j] == 0:
        del P[i]
        PL = len(P)
        i = i - 1
        break
    else:
        j += 1
    i += 1
print(P)

Acabei de montar código mais eficiente, que leva 60 segundos:

    import time
    inicio = time.time()
    print(inicio)
    m = 2702000
    P = [2] + [3] + [5] + [x for x in range(7,m,2) if x % 3 != 0 and x % 5 != 0]
    PL = len(P)
    C = {P[i] for i in range(15, PL) for j in range(3, int(P[i] ** (1/2))) if P[i] % P[j] == 0}
    P = [P[i] for i in range(PL) if not(P[i] in C)]
    print(P)
    fim = time.time()
    print(fim)
    print("duração: ", fim - inicio)

O seguinte código monta a série de primos até 2.000.000 em meio segundo. Para o número sugerido no problema (2.750.159), estoura a memória de meu jupyter. É possível que em outro noteook rode normal:

    inicio = time.time()
    print(inicio)
    m = 2000000
    P = [2] + [3] + [5] + [x for x in range(7,m,2) if x % 3 != 0 and x % 5 != 0]
    PL = len(P)
    C = {P[i] * P[j] for i in range(3, int(m ** (1/2))) for j in range(i, int(m ** (1/2)))}
    P = [P[i] for i in range(PL) if not(P[i] in C)]
    print(P)
    fim = time.time()
    print(fim)
    print("duração: ", fim - inicio)
1
  • não sei se entndi bm seu algortimo - o tempo é bom, mas não sei por que consome tanta memória. Provavelmente durant a criação do set o Python guarda os resultados repetidos temporariamente. Fiz aqui usando o "crivo de Erastotenes" - em vez de gerar todos os números não primos possíveis e ver quais núemros não estao a lista, começo com uma lista de todos os números corte os que são múltiplos dos anteriores.
    – jsbueno
    Commented 7/12/2020 às 23:07
-1

Eu acho que o jeito mais eficiente é, para cada número testar se ele é divisível por algum dos primos menores do que ele. Exemplo:

primos = [2, 3, 5]
...  # Para cada número entre 6 e 200000 define se ele é ou não primo
if num_e_primo:
    primos.append(num)

Para 6 basta testar se ele é divisivel por 2, 3, ou 5. Para 10 teste para 2, 3, 5, e 7 Assim por diante...

Não é necessario testar por todos os numeros, apenas os primos

Exemplo:

Se x for divisivel por 30, ele será divisivel por 2, 3, 5, 6, 10, 15.

-3

testa esse aqui:

"""
Created on Mon Jun 24 14:55:40 2019

@author: Tiago C. Coura
"""

def primeirosprimos(x):


    seq=[2,3,5]
    a=0
    controler=0
    while True:

        a+=1

        if a%2==0:
            r1=3*a+5
        else:
            r1=3*a+4
        if r1%5==0:
            pass
        else:
            z= len(seq)/2
            for loop in seq[0:z]:
                if r1%loop==0 :
                   controler+=1
                   break
            if controler > 0:
                controler=0
                pass
            else:
                seq.append(r1)

        if len(seq)>x-1:
            break

    return seq

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .