Найти - Пользователи
Полная версия: Разминка для мозга (projecteuler.net)
Начало » Python для новичков » Разминка для мозга (projecteuler.net)
1 2 3
zipsetic
Вот наткнулся на такую прекрасную задачку, кстати только пятую по счету))
Условие…
Найти наименьшее целое число, которое нацело делится на все числа от 1 до 20…
ХА-ХА! Вот почему-то только мой “шедевр” загружает CPU на 100%, и в таком состоянии оставляет его на долго (число я так и не узнал)))

Портированный бейсик)):
a = 20 # С этого числа начнется проверка на деление
s = [] 
for i in range(1, 21):
    s.append(i) 
i = 0 
while 1: 
    if a % s[i] == 0:    
        i += 1
        if i == 20:
            print(a)
            break
        continue
    else:
        a += 1 
        i =0

Вообще логично было бы предположить, что если умножить все числа от 1 до 20 друг на друга, то результат будет от части удовлетворять условию, но не факт, что получившееся число будет наименьшим…
Думаю, от этого и нужно отталкиваться, вот только как…

P.S подправил некоторые ошибки…


P.P.S
Мда… стоило только самому подумать… исправил пару ошибок, и все заработало!!!
Только выполнялась программа все таки долговато(секунд 30)

Но если у Вас есть альтернативные и более лаконичные варианты, то буду рад посмотреть…
Duck-Pagan
Вспомнить формулу НОК.
Вот например и алгоритм с примерами.
beelze
емнип тут достаточно перемножить все простые числа в заданном интервале
zipsetic
Пожалуй, идеальное решение!!! Взял с форума
кому интересно:
i = 1
for k in (range(1, 21)):
    if i % k > 0:
        for j in range(1, 21):
            if (i*j) % k == 0:
                i *= j
                break
print(i)
гениально!
FishHook
zipsetic
Пожалуй, идеальное решение!!! Взял с форума
кому интересно:
i = 1
for k in (range(1, 21)):
    if i % k > 0:
        for j in range(1, 21):
            if (i*j) % k == 0:
                i *= j
                break
print(i)
гениально!:D
С какого форума сей говнокод взят?
zipsetic
FishHook
С какого форума сей говнокод взят?
только не говори, что можешь лучше, докажи на деле! Покажи свой эээ… неГОВНОКОД

sp3

сравниваем на больших числах, не 21 а больше 10000
def reshetoEratosfena(n):
    resheto= list(range(2,n))
    for j in range(0,n):
        p=resheto[j]
        if p**2>n:
            break
        i=j+1
        while i<len(resheto):
            if resheto[i]%p==0:
                resheto.remove(resheto[i])
            i=i+1
    return resheto
def getMinProstMnoj(x):
    for p in prost:
        if not x % p:
            return p
    raise ValueError
def getProstmnoj(x):
    out = {}
    while x>1:
        p = getMinProstMnoj(x)
        if p not in out: out[p] = 0
        out[p] += 1
        x = x/p
    return  out
def main(maxx):
    maxstepen = {}
    global prost
    prost = reshetoEratosfena(maxx)
    for x in range(1,maxx):
        out = getProstmnoj(x)
        for p,i in out.items():
            if p not in maxstepen: maxstepen[p] = 0
            maxstepen[p] = max(i, maxstepen[p])
    nop = 1
    for p,i in maxstepen.items():
        nop *= p**i
    print (nop)
if __name__ == '__main__':
    from time import time
    t = time()
    main(10000)
    print(time() - t)

скорость получения простых чисел в этом коде вроде бы можно увеличить
Ed
Вот здесь по-моему более читабельное решение: http://stackoverflow.com/questions/147515/least-common-multiple-for-3-or-more-numbers
def gcd(a, b):
"""Return greatest common divisor using Euclid's Algorithm."""
while b:
a, b = b, a % b
return a

def lcm(a, b):
"""Return lowest common multiple."""
return a * b // gcd(a, b)

def lcmm(*args):
"""Return lcm of args."""
return reduce(lcm, args)
zipsetic
sp3
сравниваем на больших числах, не 21 а больше 10000
Круто, попытаюсь разобраться…
Ed
sp3
сравниваем на больших числах, не 21 а больше 10000
Сравнил для 3000. Хацкерский вариант ‘с форума’ отработал за 1.4 сек, ваш - за 0.05, тот, что я запостил - за 0.01
This is a "lo-fi" version of our main content. To view the full version with more information, formatting and images, please click here.
Powered by DjangoBB