代码不适用于更大的列表
Code not functioning with larger lists
我正在为项目 euler 上的一个问题编写代码。第 50 题 https://projecteuler.net/problem=50
问题是我的代码可以很好地处理小列表，特别是几千以下的素数列表，但是，它无法处理一百万以下的素数列表（大约是第 80000 个素数）这是获得答案的问题。
主要有两个问题：
- 对于大约大于 20000（10 - 20 分钟）的较大列表来说，速度非常慢
- 它没有产生正确的答案
即使逻辑正确，完成运行答案也不正确，这是内存问题吗？我想知道为什么我的代码只适用于较小的数据以及如何提高我的效率
此外，如果我问的问题不好，请告诉我。
def primes(n):
sieve = [True] * n
for i in range(3,int(n**0.5) + 1, 2):
if sieve[i]:
sieve[i * i :: 2 * i] = [False] * int((n - i * i - 1)/(2 * i) + 1)
return [2] + [i for i in range(3, n, 2) if sieve[i]]
primes = primes(1000)
start = 0
answer = 0
x = 0
count = y = 2
while len(primes[x:y - 1]) < len(primes):
summed = sum(primes[x:y])
length = len(primes[x:y])
if summed in primes and length > start:
start = length
answer = summed
x += 1
y += 1
if y - 1 == len(primes):
count += 1
x = 0
y = count
print(start)
print(answer)
如评论中所述，您的代码中存在一些不必要的线性复杂性，例如用于确定当前总和中元素的数量，或者该数字是否在素数列表中。如果你消除这些，你的算法会变得更快。
p_set = set(primes) # use a set for lookup
summed = None
while y - 1 - x < len(primes):
# instead of getting the sublist and the sum, just update the last sum
summed = sum(primes[x:y]) if summed is None else summed - primes[x-1] + primes[y-1]
length = y - x # no need for creating the sublist
if summed in p_set and length > start: # lookup in set
start = length
answer = summed
print(start, answer)
x += 1
y += 1
if y - 1 == len(primes):
count += 1
x = 0
y = count
summed = None # reset sum
但根据您的计算机，这可能仍需要一分多钟。这是因为您首先通过移动 x 和 y 来测试两个素数的所有总和，然后是三个素数的所有总和，然后增加两者之间的差异。
如果反过来，首先查看许多小素数的总和，而不是几个大素数的总和，您会很快找到结果 -- 从第三个素数开始！
max_ = res = 0
for i in range(len(primes)):
sum_ = primes[i]
for k in range(i+1, len(primes)):
sum_ += primes[k]
if sum_ in p_set and k - (i - 1) > max_:
max_, res = k - (i - 1), sum_
print(max_, res, i, k)
if sum_ > MAX:
break
我采用了另一种方法
我检查了素数列表中的每个元素是否有一个连续的序列，比到那时为止找到的最长序列长，并且其总和是素数
生成素数
import itertools
def primes(n):
found_primes = [True] * (n + 1)
for i in range(2, n + 1):
if found_primes[i]:
yield i
for j in itertools.takewhile(lambda x: x * i <= n, itertools.count(1)):
found_primes[j * i] = False
找到更长的连续总和
def find_longer_consecutive_sums(elements):
n = len(elements)
elements_set = set(elements)
max_elements = 1
max_prime = elements[-1]
for i in range(len(elements) - 1):
if sum(elements[i: i + max_elements]) > max_prime:
return
for j, k in enumerate(itertools.islice(itertools.accumulate(elements[i:]), max_elements, len(elements)), max_elements + 1):
if k in elements_set:
max_elements = j
yield i, j, k
- 我用了一个集合来检查它是否在，因为集合有固定的时间搜索
- 如果不可能有不超过最大查找素数的更长集合，我就停止了迭代
- 我对
enumerate、accumulate 和 islice 使用了一些 itertools 魔法来：
- 寻找更长的系列：(
itertools.islice(x, max_elements, len(elements))
- 在从素数列表中的特定位置开始的总和中：
itertools.accumulate(elements[i:])
连在一起
primes_list = list(primes(1000000))
results_longer = {}
for i, j, k in find_longer_consecutive_sums(primes_list):
selected_primes = primes_list[i:i+j]
print(i, j, k, sum(selected_primes), selected_primes)
results_longer[(j, i, k)] = selected_primes
returns 一秒多一点：
0 2 5 5 [2, 3]
0 4 17 17 [2, 3, 5, 7]
0 6 41 41 [2, 3, 5, 7, 11, 13]
0 12 197 197 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, ...
0 14 281 281 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, ...
0 60 7699 7699 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31...
0 64 8893 8893 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31...
0 96 22039 22039 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ...
0 100 24133 24133 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29,...
0 102 25237 25237 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29,...
0 108 28697 28697 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29,...
0 114 32353 32353 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29,...
0 122 37561 37561 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29,...
0 124 38921 38921 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29,...
0 130 43201 43201 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29,...
0 132 44683 44683 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29,...
0 146 55837 55837 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29,...
0 152 61027 61027 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29,...
0 158 66463 66463 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29,...
0 162 70241 70241 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29,...
0 178 86453 86453 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29,...
0 192 102001 102001 [2, 3, 5, 7, 11, 13, 17, 19, 23, 2...
0 198 109147 109147 [2, 3, 5, 7, 11, 13, 17, 19, 23, 2...
0 204 116533 116533 [2, 3, 5, 7, 11, 13, 17, 19, 23, 2...
0 206 119069 119069 [2, 3, 5, 7, 11, 13, 17, 19, 23, 2...
0 208 121631 121631 [2, 3, 5, 7, 11, 13, 17, 19, 23, 2...
0 214 129419 129419 [2, 3, 5, 7, 11, 13, 17, 19, 23, 2...
0 216 132059 132059 [2, 3, 5, 7, 11, 13, 17, 19, 23, 2...
0 296 263171 263171 [2, 3, 5, 7, 11, 13, 17, 19, 23, 2...
0 308 287137 287137 [2, 3, 5, 7, 11, 13, 17, 19, 23, 2...
0 326 325019 325019 [2, 3, 5, 7, 11, 13, 17, 19, 23, 2...
0 328 329401 329401 [2, 3, 5, 7, 11, 13, 17, 19, 23, 2...
0 330 333821 333821 [2, 3, 5, 7, 11, 13, 17, 19, 23, 2...
0 332 338279 338279 [2, 3, 5, 7, 11, 13, 17, 19, 23, 2...
0 334 342761 342761 [2, 3, 5, 7, 11, 13, 17, 19, 23, 2...
0 342 360979 360979 [2, 3, 5, 7, 11, 13, 17, 19, 23, 2...
0 350 379667 379667 [2, 3, 5, 7, 11, 13, 17, 19, 23, 2...
0 356 393961 393961 [2, 3, 5, 7, 11, 13, 17, 19, 23, 2...
0 358 398771 398771 [2, 3, 5, 7, 11, 13, 17, 19, 23, 2...
0 426 581921 581921 [2, 3, 5, 7, 11, 13, 17, 19, 23, 2...
0 446 642869 642869 [2, 3, 5, 7, 11, 13, 17, 19, 23, 2...
0 458 681257 681257 [2, 3, 5, 7, 11, 13, 17, 19, 23, 2...
0 460 687767 687767 [2, 3, 5, 7, 11, 13, 17, 19, 23, 2...
0 464 700897 700897 [2, 3, 5, 7, 11, 13, 17, 19, 23, 2...
0 480 754573 754573 [2, 3, 5, 7, 11, 13, 17, 19, 23, 2...
0 484 768373 768373 [2, 3, 5, 7, 11, 13, 17, 19, 23, 2...
0 488 782263 782263 [2, 3, 5, 7, 11, 13, 17, 19, 23, 2...
0 512 868151 868151 [2, 3, 5, 7, 11, 13, 17, 19, 23, 2...
0 530 935507 935507 [2, 3, 5, 7, 11, 13, 17, 19, 23, 2...
0 536 958577 958577 [2, 3, 5, 7, 11, 13, 17, 19, 23, 2...
2 537 970219 970219 [5, 7, 11, 13, 17, 19, 23, 29, 31,...
2 539 978037 978037 [5, 7, 11, 13, 17, 19, 23, 29, 31,...
3 543 997651 997651 [7, 11, 13, 17, 19, 23, 29, 31, 37...
我正在为项目 euler 上的一个问题编写代码。第 50 题 https://projecteuler.net/problem=50
问题是我的代码可以很好地处理小列表，特别是几千以下的素数列表，但是，它无法处理一百万以下的素数列表（大约是第 80000 个素数）这是获得答案的问题。
主要有两个问题：
- 对于大约大于 20000（10 - 20 分钟）的较大列表来说，速度非常慢
- 它没有产生正确的答案
即使逻辑正确，完成运行答案也不正确，这是内存问题吗？我想知道为什么我的代码只适用于较小的数据以及如何提高我的效率
此外，如果我问的问题不好，请告诉我。
def primes(n):
sieve = [True] * n
for i in range(3,int(n**0.5) + 1, 2):
if sieve[i]:
sieve[i * i :: 2 * i] = [False] * int((n - i * i - 1)/(2 * i) + 1)
return [2] + [i for i in range(3, n, 2) if sieve[i]]
primes = primes(1000)
start = 0
answer = 0
x = 0
count = y = 2
while len(primes[x:y - 1]) < len(primes):
summed = sum(primes[x:y])
length = len(primes[x:y])
if summed in primes and length > start:
start = length
answer = summed
x += 1
y += 1
if y - 1 == len(primes):
count += 1
x = 0
y = count
print(start)
print(answer)
如评论中所述，您的代码中存在一些不必要的线性复杂性，例如用于确定当前总和中元素的数量，或者该数字是否在素数列表中。如果你消除这些，你的算法会变得更快。
p_set = set(primes) # use a set for lookup
summed = None
while y - 1 - x < len(primes):
# instead of getting the sublist and the sum, just update the last sum
summed = sum(primes[x:y]) if summed is None else summed - primes[x-1] + primes[y-1]
length = y - x # no need for creating the sublist
if summed in p_set and length > start: # lookup in set
start = length
answer = summed
print(start, answer)
x += 1
y += 1
if y - 1 == len(primes):
count += 1
x = 0
y = count
summed = None # reset sum
但根据您的计算机，这可能仍需要一分多钟。这是因为您首先通过移动 x 和 y 来测试两个素数的所有总和，然后是三个素数的所有总和，然后增加两者之间的差异。
如果反过来，首先查看许多小素数的总和，而不是几个大素数的总和，您会很快找到结果 -- 从第三个素数开始！
max_ = res = 0
for i in range(len(primes)):
sum_ = primes[i]
for k in range(i+1, len(primes)):
sum_ += primes[k]
if sum_ in p_set and k - (i - 1) > max_:
max_, res = k - (i - 1), sum_
print(max_, res, i, k)
if sum_ > MAX:
break
我采用了另一种方法
我检查了素数列表中的每个元素是否有一个连续的序列，比到那时为止找到的最长序列长，并且其总和是素数
生成素数
import itertools
def primes(n):
found_primes = [True] * (n + 1)
for i in range(2, n + 1):
if found_primes[i]:
yield i
for j in itertools.takewhile(lambda x: x * i <= n, itertools.count(1)):
found_primes[j * i] = False
找到更长的连续总和
def find_longer_consecutive_sums(elements):
n = len(elements)
elements_set = set(elements)
max_elements = 1
max_prime = elements[-1]
for i in range(len(elements) - 1):
if sum(elements[i: i + max_elements]) > max_prime:
return
for j, k in enumerate(itertools.islice(itertools.accumulate(elements[i:]), max_elements, len(elements)), max_elements + 1):
if k in elements_set:
max_elements = j
yield i, j, k
- 我用了一个集合来检查它是否在，因为集合有固定的时间搜索
- 如果不可能有不超过最大查找素数的更长集合，我就停止了迭代
- 我对
enumerate、accumulate和islice使用了一些 itertools 魔法来：- 寻找更长的系列：(
itertools.islice(x, max_elements, len(elements)) - 在从素数列表中的特定位置开始的总和中：
itertools.accumulate(elements[i:])
- 寻找更长的系列：(
连在一起
primes_list = list(primes(1000000))
results_longer = {}
for i, j, k in find_longer_consecutive_sums(primes_list):
selected_primes = primes_list[i:i+j]
print(i, j, k, sum(selected_primes), selected_primes)
results_longer[(j, i, k)] = selected_primes
returns 一秒多一点：
0 2 5 5 [2, 3]
0 4 17 17 [2, 3, 5, 7]
0 6 41 41 [2, 3, 5, 7, 11, 13]
0 12 197 197 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, ...
0 14 281 281 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, ...
0 60 7699 7699 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31...
0 64 8893 8893 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31...
0 96 22039 22039 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ...
0 100 24133 24133 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29,...
0 102 25237 25237 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29,...
0 108 28697 28697 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29,...
0 114 32353 32353 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29,...
0 122 37561 37561 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29,...
0 124 38921 38921 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29,...
0 130 43201 43201 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29,...
0 132 44683 44683 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29,...
0 146 55837 55837 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29,...
0 152 61027 61027 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29,...
0 158 66463 66463 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29,...
0 162 70241 70241 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29,...
0 178 86453 86453 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29,...
0 192 102001 102001 [2, 3, 5, 7, 11, 13, 17, 19, 23, 2...
0 198 109147 109147 [2, 3, 5, 7, 11, 13, 17, 19, 23, 2...
0 204 116533 116533 [2, 3, 5, 7, 11, 13, 17, 19, 23, 2...
0 206 119069 119069 [2, 3, 5, 7, 11, 13, 17, 19, 23, 2...
0 208 121631 121631 [2, 3, 5, 7, 11, 13, 17, 19, 23, 2...
0 214 129419 129419 [2, 3, 5, 7, 11, 13, 17, 19, 23, 2...
0 216 132059 132059 [2, 3, 5, 7, 11, 13, 17, 19, 23, 2...
0 296 263171 263171 [2, 3, 5, 7, 11, 13, 17, 19, 23, 2...
0 308 287137 287137 [2, 3, 5, 7, 11, 13, 17, 19, 23, 2...
0 326 325019 325019 [2, 3, 5, 7, 11, 13, 17, 19, 23, 2...
0 328 329401 329401 [2, 3, 5, 7, 11, 13, 17, 19, 23, 2...
0 330 333821 333821 [2, 3, 5, 7, 11, 13, 17, 19, 23, 2...
0 332 338279 338279 [2, 3, 5, 7, 11, 13, 17, 19, 23, 2...
0 334 342761 342761 [2, 3, 5, 7, 11, 13, 17, 19, 23, 2...
0 342 360979 360979 [2, 3, 5, 7, 11, 13, 17, 19, 23, 2...
0 350 379667 379667 [2, 3, 5, 7, 11, 13, 17, 19, 23, 2...
0 356 393961 393961 [2, 3, 5, 7, 11, 13, 17, 19, 23, 2...
0 358 398771 398771 [2, 3, 5, 7, 11, 13, 17, 19, 23, 2...
0 426 581921 581921 [2, 3, 5, 7, 11, 13, 17, 19, 23, 2...
0 446 642869 642869 [2, 3, 5, 7, 11, 13, 17, 19, 23, 2...
0 458 681257 681257 [2, 3, 5, 7, 11, 13, 17, 19, 23, 2...
0 460 687767 687767 [2, 3, 5, 7, 11, 13, 17, 19, 23, 2...
0 464 700897 700897 [2, 3, 5, 7, 11, 13, 17, 19, 23, 2...
0 480 754573 754573 [2, 3, 5, 7, 11, 13, 17, 19, 23, 2...
0 484 768373 768373 [2, 3, 5, 7, 11, 13, 17, 19, 23, 2...
0 488 782263 782263 [2, 3, 5, 7, 11, 13, 17, 19, 23, 2...
0 512 868151 868151 [2, 3, 5, 7, 11, 13, 17, 19, 23, 2...
0 530 935507 935507 [2, 3, 5, 7, 11, 13, 17, 19, 23, 2...
0 536 958577 958577 [2, 3, 5, 7, 11, 13, 17, 19, 23, 2...
2 537 970219 970219 [5, 7, 11, 13, 17, 19, 23, 29, 31,...
2 539 978037 978037 [5, 7, 11, 13, 17, 19, 23, 29, 31,...
3 543 997651 997651 [7, 11, 13, 17, 19, 23, 29, 31, 37...