Пусть S — сумма всех простых натуральных делителей целого числа, не считая самого числа. Если таких делителей у числа нет, то считаем значение S равным нулю.
Напишите программу, которая перебирает целые числа, меньшие 1 475 000, в порядке убывания и ищет среди них такие, для которых значение S не равно нулю, не больше 42 000 и кратно 6. В ответе запишите первые пять найденных чисел в порядке убывания.
Например, для числа 10S = 2 + 5 = 7.
Ответ:
Приведём решение на языке Python.
def prime(n):
for i in range (2, int(n**0.5)+1):
if n%i==0: return False
return True
k = 1475000 - 1
count = 0
while count != 5:
delitel = []
for i in range(2, int(k**0.5)+1):
if k%i == 0:
if prime(i):
delitel.append(i)
if prime(k // i):
delitel.append(k//i)
if len(delitel) > 0:
s = sum(delitel)
if s <= 42000 and s%6 ==0:
print(k)
count += 1
k -= 1
В результате работы программа должна вывести следующее:
1474997
1474992
1474973
1474968
1474954
Ответ: 1474997 1474992 1474973 1474968 1474954.
Приведём решение Юрия Красильникова на языке Python.
def prostoe(n):
k=2
while k**2 <= n:
if n%k==0: return False
k+=1
return True
n,m = 1475000,0
while m < 5:
n-=1
k=2
d=set()
while k**2 <= n:
if n%k==0: d |= {k,n//k}
k+=1
sn = sum(x for x in d if prostoe(x))
if sn > 0 and sn <= 42000 and sn%6==0:
print(n)
m+=1