Пусть M — сумма максимального и минимального простых делителей целого числа, не считая единицы и самого числа. Если у числа нет простых делителей, то считаем значение M равным нулю. Напишите программу, которая перебирает целые числа, большие 7 500 000, в порядке возрастания и ищет среди них первые пять таких чисел, для которых M заканчивается на 32 и кратно общему количеству простых делителей.
Приведём решение на языке Python.
def prime(n):
for i in range (2, int(n**0.5)+1):
if n%i==0: return False
return True
def divs(n):
count = 0
div = []
for i in range(2, n//2 + 1):
if n%i == 0 and prime(i):
div.append(i)
count += 1
return count, div
k = 7500000
counter = 0
while True:
c, d = divs(k)
if c >= 2:
s = d[0] + d[-1]
if s%100 == 32 and s%c == 0:
print(k)
counter += 1
if counter == 5: break
k += 1
В результате работы программа должна вывести следующее:
7500045
7500107
7500131
7500317
7500589
Приведём решение Юрия Красильникова на языке Python.
def prostoe(n):
k=2
while k**2<=n:
if n%k==0: return False
k+=1
return True
def prostdel(n):
d=set()
k=2
while k**2<=n:
if n%k==0: d|={k,n//k}
k+=1
return sorted([x for x in d if prostoe(x)])
n=7500001
k=0
while k<5:
p=prostdel(n)
if p and (p[0]+p[-1])%100==32 and (p[0]+p[-1])%len(p)==0:
print(n)
k+=1
n+=1