DjangoBB LoFi version

Полная версия: Еще одна задачка с эйлера

Начало » Python для новичков » Еще одна задачка с эйлера

pasaranax

Март 9, 2010 00:20:42

Есть такие числа, которые называются "треугольными", это похоже на факториал, только вместо умножения используется сложение. Например: 1+2+3+4=10, 10 - треугольное число. Нужно найти самое маленькое треугольное число, которое имеет более 500 делителей.
Генератор треугольных чисел - фигня, а вот как быстро посчитать количество делителей - это проблема. Приветствуются самые быстрые и красивые решения :)

pyuser

Март 9, 2010 04:32:41

первое, что пришло в голову:

import math
2 if math.modf(math.sqrt(n))[0] else 1) + \
            2 * sum([1 for i in xrange(2, long(math.sqrt(n)) + 1) if 0 == n % i]

одно НО, число, имеющее 500 делителей выходит за границы диапазона целых на ПК :(

Striver

Март 9, 2010 08:53:13

Подсчет всего числа делителей прямо связан с разложением на простые множители.
Если n=(p1**k1)*(p2**k2)*…*(pm**km), где p1…pm - простые числа, то, как я понял, число делителей у этого n равно (k1+1)*(k2+1)*…(km+1)

Разложение на простые множители считается сложной математической проблемой, но числа с порядка 500 делителями это фигня, можно и по-колхозному проверять, времени немного займёт. Я лет 5 назад писал функцию:

def S_Rno(n):           
    if n > 10**11:
        #Выход за пределы допустимого диапазона, определяется размером списка простых чисел
        raise ValueError     
    if n==1: return {1:0}
    n1=int(n**(0.5))
    delit={}
    ind=0
    k=simples[ind]
    while n!=1:
        i=0
        while n%k ==0:
            i+=1
            n/=k
        if i:
            delit[k]=i
            n1=int(n**(0.5))
        if k>n1 and n!=1:
            delit[n]=1
            break
        ind+=1
        k=simples[ind]
    return delit

здесь simples - заранее созданный список простых чисел. Для чисел меньше 1000000 его размер 78498 чисел. Можно создать такой функцией:

def Simple(n):
    ret=[2]
    iroots=0
    k=2
    for i in xrange(3,n):
        flag=0
        for j in xrange(iroots+1):
            if i%ret[j] == 0:
                flag=1
                break
        if flag:
            continue
        ret.append(i)
        iroot=i**(0.5)
        while ret[iroots]<iroot:
            iroots+=1
    return ret

Мне тогда нужно было много разложений делать, поэтому я однажды создал такой список и сохранил в файл, а потом импортировал просто.

Striver

Март 9, 2010 13:43:55

Вобщем вот полное решение:

# -*- coding: cp1251 -*-

from simple import simples      # список простых чисел до 1000000

#----- Разложение на множители -------------
def S_Rno(n):           # проверка с использованием простых чисел
    if n > 10**12:
        raise ValueError     #Число выходит за пределы допустимого диапазона
    if n==1: return {1:0}
    n1=int(n**(0.5))
    delit={}
    ind=0
    k=simples[ind]
    while n!=1:
        i=0
        while n%k ==0:
            i+=1
            n/=k
        if i:
            delit[k]=i
            n1=int(n**(0.5))
        if k>n1 and n!=1:
            delit[n]=1
            break
        ind+=1
        k=simples[ind]
    return delit

#--- Число делителей ---------
def deliteley(n):
    d=S_Rno(n)
    P=1
    for st in d.values():
        P*=(st+1)
    return P

#---- Вычисляем n-е треугольное число -----
def Treug(n):
    return n*(n+1)/2

#---- Проверяем все числа до n ----------
def prov(n,k):
    for i in xrange(1,n):
        T=Treug(i)
        if i%10000==0:
            print 'i=',i,'T=',T
        d=deliteley(T)
        if d>k:
            print 'i=',i,'T=',T,'d=',d
            return T
    return 'None'

prov(20000,500)

Результат получен за пару секунд:
i= 12375 T= 76576500 d= 576
76576500

Zubchick

Март 9, 2010 18:32:48

>> (k1+1)*(k2+1)*…(km+1)
28 = 2**2 * 7
по вашей формуле число его делителей (2 + 1) * (1 + 1) = 6 так?
А на самом деле это только 2, 4, 7, 14 то есть 4.

UPD Кажется был не прав, формула считает делителями еще само число и единицу…

baa

Янв. 12, 2012 08:52:11

i = n = D = 0
while D < 500:
    i += 1
    n += i
    if n % (2*3*5*7) != 0: 
        continue
    d = 2
    for j in xrange(2, int(n**0.5) + 1):
        if n % j == 0: 
            d += 2
        if j * j == n: 
            d -= 1
    D = max(D, d)
print i, n, D # 12375 76576500 576 time 0.843182086945