Проверял ли я каждый последующий набор в этом списке? - PullRequest
Новая
       6

Проверял ли я каждый последующий набор в этом списке?

2 голосов
/ 02 мая 2010

Я пытаюсь решить проблему 50 на Project Euler . Не дайте мне ответ или не решите его для меня, просто попробуйте ответить на этот конкретный вопрос.

Цель состоит в том, чтобы найти самую длинную сумму последовательных простых чисел, которая добавляет к простому числу меньше миллиона. Я написал сито, чтобы найти все простые числа ниже n, и я подтвердил, что это правильно. Далее я собираюсь проверить сумму каждого подмножества последовательных простых чисел, используя следующий метод:

У меня есть пустой список sums. Для каждого простого числа я добавляю его к каждому элементу в sums и проверяю новую сумму, затем добавляю простое число к sums.

Вот оно в питоне 

primes = allPrimesBelow(1000000)
sums = []
for p in primes:
    for i in range(len(sums)):
        sums[i] += p
        check(sums[i])
    sums.append(p)

Я хочу знать, звонил ли я по номеру check() для каждой суммы двух или более последовательных простых чисел ниже миллиона

Проблема говорит о том, что есть простое число 953, которое можно записать как сумму 21 последовательных простых чисел, но я не нахожу ее.

Ответы [ 2 ]

5 голосов
/ 02 мая 2010

Ваш код правильный.Я запустил его, и он генерирует число 953, поэтому проблема, вероятно, связана с вашей основной функцией генерации.Должно быть 78498 простых чисел ниже миллиона - возможно, вы захотите проверить, получили ли вы этот результат.

При этом ваш код будет выполняться долго, так как он вызовет check () 3 080 928 753 раза.Возможно, вы захотите найти метод, который проверяет меньше сумм.Я не буду останавливаться на этом, поскольку вы просили не спойлеры, но дайте мне знать, если вы заинтересованы в общих подсказках.

0 голосов
/ 02 мая 2010

У меня нет прямого ответа от макушки головы, но вы пробовали делать суммы во вложенном массиве и затем добавлять простые числа p к подмассивам вместо добавления их к счетчику суммирования? Это позволило бы вам визуально проверить, какие простые числа были добавлены к каждому подмассиву, и, соответственно, подсказать, какие простые числа суммировали в исходном коде.

...