Início / coding / Perguntas / 79430009
Accepted
Peter4075
Asked: 2025-02-11 20:43:54 +0800 CST

Projeto de Euler 27 - como substituir uma lista 2D por uma lista 1D?

  • 772

Eu escrevi uma solução Python para o problema 27 do Projeto Euler. Ela funciona, mas é geologicamente lenta (1765 segundos para encontrar o resultado correto de -59.231). Para acelerar as coisas, eu gostaria de substituir a gigantesca lista 2D "box" por uma lista 1D? Minha pergunta é, como eu faço isso? Aqui está o problema: Projeto Euler 27 E aqui está meu código:

import time
from sympy import isprime

start_time = time.time()

a_lower_limit = -999
a_upper_limit = 1000
b_lower_limit = 0
b_upper_limit = 1001
a1 = abs(a_lower_limit)
a2 = a_upper_limit - a_lower_limit
b2 = b_upper_limit - b_lower_limit

# 2d list of primes for permutations of a, b
box = [[] for j in range(a2 * b2)] 
# 2d list of a*b for each a, b permutation
box_ab = [[] for j in range(a2 * b2)] 

for a in range(a_lower_limit, a_upper_limit):
    for b in range(b_lower_limit, b_upper_limit):
        a_prime = a + a1       
        for n in range(0, b_upper_limit):                       
            num = n**2 + a*n + b
            if isprime(num):         
                   box[(a_prime * b2) + b].append(num) 
                   box_ab[(a_prime * b2) + b].append(a*b)

# Define a function that finds the longest sub-list in "box"
def max_length_list(box):
    max_length = max(len(x) for x in box)
    max_list = max(box, key=len)
    return (max_list)

# Find index of max_length_list in box
x = box.index(max_length_list(box))

# Product of coefficients a and b that produce the longest sub-list in "box"
print((box_ab[x])[0]) 

print(f"Run time: {(time.time() - start_time):.2f} seconds")

Para cada permutação de a e b, o código encontra o número de primos gerados para valores consecutivos de n, começando com n = 0. Eles são então armazenados em diferentes sublistas na lista 2D “box”. Eu gostaria de substituir esta “box” 2D por uma lista: box = [] e uma variável max_number_primes, inicialmente definida como zero. Para cada permutação de a e b, os primos gerados precisam ser armazenados na lista “box”. Após cada permutação, eu gostaria de comparar len(box) com max_number_primes. Se len(box) > max_number_primes, então max_number_primes = len(box). Eventualmente, eu obterei o maior max_number_primes possível. Eu posso então tentar encontrar o a*b correspondente.

Isto (e variações disto) é o que eu tentei. Mas não consigo fazer funcionar.

a_lower_limit = -999
a_upper_limit = 1000
b_lower_limit = 0 # for now, always set to zero
b_upper_limit = 1001
a1 = abs(a_lower_limit)
b1 = abs(b_lower_limit) # don't need this if b_lower_limit set to zero
a2 = a_upper_limit - a_lower_limit
b2 = b_upper_limit - b_lower_limit

box = [] #  list of primes
max_number_primes = 0

for a in range(a_lower_limit, a_upper_limit):
    for b in range(b_lower_limit, b_upper_limit):
        if a_lower_limit < 0:
            a_prime = a + a1
        else:
            a_prime = a - a_lower_limit       
        for n in range(0, b_upper_limit):                       
            num = n**2 + a*n + b
            if isprime(num):         
                box.append(num)
                if len(box) > max_number_primes:
                    max_number_primes = len(box)
                    box.clear
python

1 respostas

  1. Best Answer

    Pode haver alguns atalhos para isso (não sou matemático), mas acho que loops aninhados simples são eficientes neste caso:

    import sympy
import time
from functools import cache
from collections.abc import Iterator

@cache
def isprime(p: int) -> bool:
    return sympy.isprime(p)

# Sieve of Eratosthenes
# CREDIT: David Eppstein, UC Irvine, 28 Feb 2002
def sieve() -> Iterator[int]:
    D = {}
    q = 2
    while True:
        if q not in D:
            yield q
            D[q * q] = [q]
        else:
            for p in D[q]:
                D.setdefault(p + q, []).append(p)
            del D[q]
        q += 1

def genprimes(limit: int) -> Iterator[int]:
    for p in sieve():
        if p > limit:
            break
        yield p

if __name__ == "__main__":
    A = B = m = 0
    start = time.perf_counter()
    primes = list(genprimes(1000))
    for a in range(-999, 1000, 2):
        for b in primes:
            n = 1
            while isprime(n * n + a * n + b):
                n += 1
            if n > m:
                A, B = a, b
                m = n

    duration = time.perf_counter() - start
    print(f"{A=:,d} {B=:,d} C={A*B:,d} {m=:,d} {duration=:.4f}s")

    Saída:

    A=-61 B=971 C=-59,231 m=71 duration=0.0305s
    • 1

relate perguntas