Ещё одна задачка!
В общем вот условие:
Последовательность треугольных чисел образуется путем сложения натуральных чисел. К примеру, 7-ое треугольное число будет 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. Первые десять треугольных чисел:
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
Перечислим делители первых семи треугольных чисел:
1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28
Как мы видим, 28 - первое треугольное число, у которого более пяти делителей.
Каково первое треугольное число, у которого более пятисот делителей?
Вот моё топорное решение, которое при 500 делителях уже ищет долго-долго:
Код:
m=0
n=[]
x=0
y=10001
for r in range(2, 10001):
for j in range(1, r):
m=m+j
n.append(m)
m=0
for k in range(9999):
if n[k]%2==0:
for l in range(1,int(n[k]/2)+1):
if n[k]%l==0:
x+=1
if x==500:
break
x=0
print n[k]
Как можно оптимизировать, или это задача не так решается? Нашел в интернете инфу, что надо воспользоваться факторизацией чисел. В общем математическая часть понятна, а вот как это перенести на компьютерный язык теряюсь. В общем остановился вот на этом:
Код:
m=0
n=[]
x=0
y=1001
for r in range(2, 1001):
for j in range(1, r):
m=m+j
n.append(m)
m=0
t=1000
lst=[]
a=range(t+1)
a[1]=0
i=2
while i<=t:
if a[i]!=0:
lst.append(a[i])
for q in xrange(i, t+1, i):
a[q]=0
i+=1
l=0
d=0
h=0
w=[]
count=0
mul=1
for b in range(y-2):
for s in range(t):
while lst[s]<=n[b]:
for d in range(n[b]):
if n[b]%lst[s]==0:
l+=1
w.append(l)
for z in range(len(w)):
count=w[z]+1
mul=mul*count
if mul>5:
print n[b]
break
l=0
При запускании ошибка Out of Range! Но это ладно можно подкорректировать. Тут уже видна ошибка, при делении например числа 28 на простые числа, как сделать так, что когда он делится на 2 что еще по циклу проверилось делится ли ещё раз на это простое число?
