Решение 23 задачи проекта Эйлера на python
Решаю 23 задачу из проекта Эйлера. Моя идея состоит в том, что перебирая все числа от 1 до 28123, я нахожу среди них избыточные и добавляю в список, а затем проверяю, может ли число быть представлено, как сумма двух избыточных чисел из этого списка. Если может, то я вычитаю это число из суммы всех чисел от 1 до 28123. Таким образом, в сухом остатке я должен получить сумму чисел, которые не могут быть представлены как сумма двух избыточных чисел. Реализация на языке:
array = []
summ = 0
for i in range (1, 28123):
summ += i
for i in range (4, 28123):
print ("Идет обработка числа ", i)
if i % 2 == 0:
n = 1
j = 2
limit = i // 2
if limit in array:
array.append (i)
continue
else:
n = 2
j = 3
limit = i // 3
sum_dividers = 1
while (sum_dividers <= i) and (j <= limit):
if i % j == 0:
sum_dividers += j
j += n
if sum_dividers > i:
array.append (i)
mean = i // 2
for j in array:
if (i - j) in array:
summ -= i
break
elif j > mean:
break
print (summ)
Во втором цикле я начинаю с числа 4, так как ни 1, ни 2, ни 3 - не избыточные числа, и не могут быть представлены как сумма двух избыточных чисел. А прописывать для них отдельные случаи я не вижу смысла.
Я понимаю, что мой код плохо оптимизирован, над этим я буду работать потом. Сейчас меня интересует, почему он выдает неправильный ответ? Верное решение - 4179871, мой код говорит, что 53218451, то есть разница огромная. В чем проблема?
Ответы (2 шт):
мой код даёт 4179871
# проверить, является ли число избыточным
def is_redundant(value):
res = 0
for i in range(1, value):
if value % i == 0:
res += i
return res > value
# проверить, является ли число суммой двух избыточных чисел
def is_redundans_sum(value, redundants):
# рассмотреть все варианты первого слагаемого
for i in redundants:
sub = value - i
# проверить - является ли разность избыточным числом
if sub in redundants:
return True
return False
# получить список всех избыточных чисел
limit = 28123
redundants = {i for i in range(1, limit + 1) if is_redundant(i) is True}
# определить какое число является суммой двух избыточных чисел
res = 0
for value in range(1, limit + 1):
res += 0 if is_redundans_sum(value, redundants) is True else value
print(res)
работает 26,2 сек, основная оптимизация сделана на определении суммы - я прохожу по всем избыточным числам, а затем проверяю, является ли разность избыточным числом (для множества поиск числа в списке выполняется за очень короткое время)
версия 2:
12.8 сек:
основное время уходит на составление списка избыточных чисел (O(n^2) сложность все таки)
главная оптимизация - множители надо считать только до половины числа, дальше множителей нет
второстепенная оптимизация - рассматривать первый множитель только до проверяемого числа и не больше, но для этого приходится использовать список, а не множество (так как нужны отсортированные числа, а множество это обеспечить не может)
# проверить, является ли число избыточным
def is_redundant(value):
res = 1
for i in range(2, value // 2 + 1):
if value % i == 0:
res += i
return res > value
# проверить, является ли число суммой двух избыточных чисел
def is_redundans_sum(value, redundants, redundants_s):
# рассмотреть все варианты первого слагаемого
for i in redundants:
# если число превышает первое слагаемое - не рассматривать числа множители дальше
if i > value:
break
# вычислить второе слагаемое
sub = value - i
# проверить - является ли разность избыточным числом
if sub in redundants_s:
return True
return False
# получить список всех избыточных чисел
limit = 28123
redundants = [i for i in range(1, limit + 1) if is_redundant(i)]
redundants_s = set(redundants)
# определить какое число является суммой двух избыточных чисел
res = 0
for value in range(1, limit + 1):
res += 0 if is_redundans_sum(value, redundants, redundants_s) else value
print(res)
Для красоты функцию is_redundant можно записать как
def is_redundant(value):
res = sum(i for i in range(1, value // 2 + 1) if value % i == 0)
return res > value
на скорость это никак не влияет :(
вариант 3:
2.24 сек:
основная оптимизация - иной подход к функции is_redundant определения избыточности числа (O(n^1.5) сложность)
проходим до множителя sqrt(value) включительно
если число i является множителем, то и value // i является множителем, учитываем и его, но...только 1 раз, для чего используется список всех чисел от 0 до value:
def is_redundant(value):
res = 1
dividers = [0] * value
dividers[0] = 1
for i in range(2, int(value**0.5) + 1):
if value % i == 0:
res += i
dividers[i] = 1
i2 = value // i
if dividers[i2] == 0:
res += i2
dividers[i2] = 1
return res > value
Вся проблема в операторе continue. Когда он выполняется у строчки summ -= i нет шансов выполнится и убрать соответствующее число. Если копию цикла for j in array: вставить перед continue, то ваша программа выдаст верный результат.
Вот быстрое решение. Применены решето Эратосфена с делителями, мультипликативность суммы делителей, два представления для множества избыточных чисел:
def make_sieve(n):
sieve = [0] * n
for i in range(2, n):
if sieve[i] == 0:
sieve[i] = i
for j in range(i * i, n, i):
if sieve[j] == 0:
sieve[j] = i
return sieve
def sum_of_divisors(n, sieve):
assert 0 < n
s = 1
j = n
while j > 1:
i = sieve[j]
j //= i
m = i * i
while sieve[j] == i:
j //= i
m *= i
s *= (m - 1) // (i - 1)
return s
sieve = make_sieve(28123 + 1)
s = 28123 * (28123 + 1) // 2
ab_dense = []
ab_sparse = [False] * (28123 + 1)
for i in range(1, 28123 + 1):
ab_sparse[i] = sum_of_divisors(i, sieve) > 2 * i
i2 = i // 2
if i % 2 == 0 and ab_sparse[i2]:
ab_dense.append(i2)
for j in ab_dense:
if ab_sparse[i - j]:
s -= i
break
print(s)