DjangoBB LoFi version

Полная версия: Задачка с области теории чисел!

Начало » Центр помощи » Задачка с области теории чисел!

Alibek24

Фев. 26, 2012 14:18:06

В общем вот условие:

Последовательность треугольных чисел образуется путем сложения натуральных чисел. К примеру, 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 что еще по циклу проверилось делится ли ещё раз на это простое число?

В общем жду критики, комментов (больше критики;) ) Изучаю питон 1 месяц

FishHook

Фев. 27, 2012 04:46:39

triangles=(sum(xrange(1,x)) for x in xrange(1,100000000))
while 1:
    n=triangles.next()
    dels=[x for x in xrange(n/2,1,-1) if n%x==0 ]
    if len(dels)>=100:
        break

print n, len(dels), dels

73920 110

Вроде работает, правда 500 делителей ищет весьма долго.
Попробуйте как-нибудь оптимизировать, как я не знаю.

baa

Фев. 27, 2012 06:42:48

x = n = D = 0

while D <= 500:

    n += 1

    x += n

    d = 2
    
    for i in xrange(2, int(x**0.5) + 1):
        
        if not x % i:
        
            d += 2
            
    D = max(D, d)
    
print x, D # 76576500 576

nerijus

Фев. 27, 2012 20:51:01

Нечего велосипед изобретать: http://www.mathblog.dk/triangle-number-with-more-than-500-divisors/

nerijus

Фев. 27, 2012 21:11:11

И вот ещё на питоне (код нашёл в интернете, немного поправил), на моем компе с i7 находит примерно за секунду:

prime_list = [2, 3, 5, 7, 11, 13, 17, 19, 23]   # Ensure that this is initialised with at least 1 prime
prime_dict = dict.fromkeys(prime_list, 1)
lastn = prime_list[-1]


def _isprime(n):
    ''' Raw check to see if n is prime. Assumes that prime_list is already populated '''
    isprime = n >= 2 and 1 or 0
    for prime in prime_list:                    # Check for factors with all primes
        if prime * prime > n: break             # ... up to sqrt(n)
        if not n % prime:
            isprime = 0
            break
    if isprime: prime_dict[n] = 1               # Maintain a dictionary for fast lookup
    return isprime

def _refresh(x):
    ''' Refreshes primes upto x '''
    global lastn
    while lastn <= x:                           # Keep working until we've got up to x
        lastn = lastn + 1                       # Check the next number
        if _isprime(lastn):
            prime_list.append(lastn)            # Maintain a list for sequential access


def prime(x):
    ''' Returns the xth prime '''
    global lastn
    while len(prime_list) <= x:                 # Keep working until we've got the xth prime
        lastn = lastn + 1                       # Check the next number
        if _isprime(lastn):
            prime_list.append(lastn)            # Maintain a list for sequential access
    return prime_list[x]

def num_factors(n):
    ''' Returns the number of factors of n, including 1 and n '''
    div = 1
    x = 0
    while n > 1:
        c = 1
        while not n % prime(x):
            c = c + 1
            n = n / prime(x)
        x = x + 1
        div = div * c
    return div

for i in xrange(1, 1000000000):
    n = i * (i+1) / 2
    if num_factors(n) > 500:
        print n
        break