def get_redundants_sum(redundants: list, limit: int):
redundants_set = set(redundants)
arr = []
for i in range(1, limit): # перебор от 1 до 28124
if all(i - j not in redundants_set for j in redundants): # если i - j нет в reduants_set добавляем
arr.append(i)
return sum(arr)def solve_by_set(abundants: list, limit: int):
abundants_set = set(abundants)
return sum(i for i in range(1, limit) if all(i - j not in abundants_set for j in abundants))from time import time, sleep
def timer(f):
def wrapper(*args, **kwargs):
t, res = time(), f(*args, **kwargs)
print(f"{f.__name__}, sec: {time() - t:f}")
return res
return wrapper
@timer
def get_redundant_nums(limit: int):
dividers = [1] * limit
for i in range(2, limit // 2 + 1):
for j in range(i * 2, limit, i):
dividers[j] += i
redundant_nums = []
dividers[0] = 0
for i, s in enumerate(dividers):
if i < s:
redundant_nums.append(i)
return redundant_nums
@timer
def get_redundants_sum(redundants: list, limit: int):
redundants_set = set(redundants)
return sum(i for i in range(1, limit) if all(i - j not in redundants_set for j in redundants))
@timer
def final(limit: int):
return get_redundants_sum(get_redundant_nums(limit), limit)
print(final(50))get_redundant_nums, sec: 0.000000
get_redundants_sum, sec: 0.000000
final, sec: 0.001018def get_izb(N: int):
sum_of_dividers = [1] * N
for i in range(2, N // 2 + 1):
for j in range(i * 2, N, i):
sum_of_dividers[j] += i
others = []
sum_of_dividers[0] = 0
for i, s in enumerate(sum_of_dividers):
if i < s:
others.append(i)
return others
def get_sum(arr: dict, N: int):
summ = []
all_nums = list(range(N))
for f in arr:
for s in arr:
s = f + s
if s > N:
break
summ.append(s)
lst = [o for o in all_nums if o not in summ]
return sum(lst)
def final(N: int):
return get_sum(get_izb(N), N)f = '''def final(N):
sum_of_dividers = [1] * N # все числа делятся на 1, проходили уже
for i in range(2, N // 2 + 1): # начнем делители с двойки
for j in range(i * 2, N, i): # ко всем ячейкам с адресом,
# кратным i но большим, чем i,
sum_of_dividers[j] += i
result = list(range(N)) # изначально все числа - кандидаты в нераскладываемые
others = [] # здесь будем копить варианты второго слагаемого
sum_of_dividers[0] = 0 # заглушим чтоб ноль не пролазил через if i < s
for i, s in enumerate(sum_of_dividers):
if i < s: # i избыточное
others.append(i) # случай i + i должен быть учтен в этом же цикле
for j in others:
j += i
if j >= N: # выход за пределы диапазона
break # в others числа по нарастающей, остальные заведомо больше
result[j] = 0
'''
def measure_time(function: str):
elapsed_time = timeit.timeit(function, number=100)/100
print(elapsed_time)
measure_time(f)