Euler -Projekt 27 - Wie ersetzt ich eine 2D -Liste durch eine 1D -Liste? ⇐ Python

[Anonymous]

Ich habe eine Python -Lösung für das Euler -Projekt Problem 27 geschrieben. Es funktioniert aber geologisch langsam (1765 Sekunden, um das richtige Ergebnis von -59.231 zu finden). Um die Dinge zu beschleunigen, möchte ich die Mammut -2D -Liste "Box" durch eine 1D -Liste ersetzen? Meine Frage ist, wie mache ich das? Hier ist das Problem:

Und hier ist mein Code: < Br />

Code: Select all

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")
< /code>
Für jede Permutation von A und B stellt der Code die Anzahl der Primzahlen fest, die für aufeinanderfolgende Werte von n generiert werden, beginnend mit n = 0. Diese werden dann in verschiedenen Unterlisten in der 2D -Liste "Box". Ich möchte dieses 2D -Box durch eine Liste ersetzen: Box = [] und eine variable max_number_primes, die zunächst auf Null gesetzt ist. Für jede Permutation von A und B müssen die erzeugten Primzahlen in der Liste „Box“ gespeichert werden. Nach jeder Permutation möchte ich Len (Box) mit max_number_primes vergleichen. Wenn Len (Box)> max_number_primes, dann max_number_primes = len (Box). Schließlich bekomme ich den größtmöglichen Max_Number_Primes. Ich kann dann versuchen, das entsprechende A*b zu finden. Aber ich kann es nicht zum Laufen bringen. < /P>
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