TOPIC

Runtime Error

Bruno Mendes de Carvalho Castelo Branco asked 2 years ago

alguém pode me ajudar? Por que estou recebendo runtime error? Os outputs estão dando todos de acordo com os inputs do uDebug. Tem outra variação do meu código que dá Time Limit Exceeded. Segue abaixo a do Runtime Error, que foi a última submissão que fiz nesse problema:

# coding: utf-8

from math import sqrt

# função para obter lista de números primos

def crivo_eratostenes(n):
    A = list(range(2, n))

    for i in range(2, int(sqrt(n) + 1)):

        if i in A:

            for j in range(i ** 2, n, i):

                if j in A:
                    A.remove(j)

    return A

primos: list = []
grupo: list = []
posicao: int = 0
n: int = 1
aux: int = 0

# entrada:

while n > 0:
    n = int(input())
    aux = n

    # computações:

    if n == 0:
        break
    else:
        remover = 0
        grupo = list(range(1, n + 1))

        while len(grupo) > len(primos) + 1:
            primos = crivo_eratostenes(aux)
            aux += 1

        while len(grupo) > 1:

            m = primos.pop(0)
            remover += (m - 1)

            while remover >= n:
                remover -= n

            del grupo[remover]
            n -= 1
        posicao = grupo.pop(0)

        # saída:

        print(posicao)

Remember not post solutions. Your post may be reviewed by our moderators.

  • Daniel Koga replied 1 year ago

    Não sei Python muito bem, mas consegui identificar alguns problemas no algorítmo.

    1- Você está chamando a rotina do crivo repetidamente somente para descobrir qual é o n-ésimo primo. Isso é um custo enorme e desnecessário! Use a seguinte relação:

    ln(N) + ln(ln(N)-1) < p(N)/N < ln(N) + ln(ln(N)) para n >= 6

    onde ln(x) é o logarítmo em base natural de x e p(N) é o n-ésimo primo. Ou seja, use como teto do crivo o valor:

    p(N) = N * ( ln(N) + ln(ln(N)) )

    Isso garantirá que você tem primos o suficiente.

    2- Usar o crivo é algo extremamente lento e custoso e você está fazendo isso em toda iteração do loop while. Pré-calcule os primos necessários somente uma vez no início do programa ao invés de recalculá-los. E ao invés de tirar os primos da lista com um pop(), simplesmente acesse-os por índice sem apagá-los.

    3- Esse teste:

    if n == 0
          break;
    else

    é desnecessário, pois a condição n == 0 nunca ocorre dentro do loop while (n > 0). Você pode tirá-lo do código.

    4- Ao invés de usar esse loop:

    while remover >= n:
          remover -= n

    use a operação módulo.