задача из Project Euler

[Alibek24]

В общем надо найти наибольший простой делитель числа 600851475143. В принципе задачу решил, но решение не очень нравиться. Кстати вот оно:

Используется синтаксис Python

 
from math import *
n=0
for c in range(2, int(sqrt(600851475143))):
    for i in range(2, c):
        if c%i==0:
            n=n+1
    if n==0 and 600851475143%c==0:
        print c 
    n=0
 

он выдает постепенно ответы и я думал выберу наибольший и все. На первой минуте выдал 4 ответа: 71, 839,1471,6857 и дальше считал. Я попробовал 6857 в ответы ввести и ответ оказался правильным. Но удовлетворения не получил. Можно ли как нибудь оптимизировать мой код? В принципе в интернете есть много алгоритмов нахождения простых чисел, и они дают выйгрыш в более чем 1000 раз, но суть вопроса можно ли мой алгоритм оптимизировать?

[tolstopuz]

Как минимум можно при нахождении очередного делителя заменить 600851475143 на частное от деления.

[Alibek24]

Цитата:

Как минимум можно при нахождении очередного делителя заменить 600851475143 на частное от деления.

так! спасибо! Что ещё?

[venco]

Alibek24 в сообщении #541631 писал(а):

Что ещё?

Проверка простоты очередного делителя занимает больше времени, чем если бы вы пробовали делить на все натуральные числа подряд. Если вы сделаете то, что сказал tolstopuz, то эта проверка не нужна - простые делители и так будут первыми. Только не забудьте, что простой делитель может встретиться несколько раз.

[Alibek24]

в общем погуглил, и наткнулся на статью на хабре: http://habrahabr.ru/blogs/algorithm/122538/ там в принципе методы понятны. в общем с этой задачей пока закончил, теперь ещё одна появилась. Вот текст задачи:

2520 - самое маленькое число, которое делится без остатка на все числа от 1 до 10.
Какое самое маленькое число делится нацело на все числа от 1 до 20?

Конечно тупой алгоритм, но всё же:

Используется синтаксис Python

n=0
for i in range(1, 100000000, 2):
    for j in range(1, 21):
        if i%j==0:
            n=n+1
            if n==20:
                print i
            else:
                print "no"
    n=0 

нотик не потянул таких мощностей. Может как то можно ускорить процесс, или подскажите другой алгоритм?

[Joker_vD]

Alibek24 в сообщении #541762 писал(а):

Какое самое маленькое число делится нацело на все числа от 1 до 20?

$\text{НОК}(1,2,\dots,20)$.
Как искать? Во-первых, $\text{НОК}(a_1,a_2,\dots,a_n)=\text{НОК}\left(\text{НОК}(a_1,a_2,\dots,a_{n-1}), a_n\right)$. Во-вторых, $\text{НОК}(a,b)=\dfrac{ab}{(a,b)}$.

[Alibek24]

это не НОК! надо найти наименьшее число делящееся на все числа от 1 до 20

[Alexu007]

232792560

[nnosipov]

Alibek24 в сообщении #541762 писал(а):

2520 - самое маленькое число, которое делится без остатка на все числа от 1 до 10. Какое самое маленькое число делится нацело на все числа от 1 до 20?

Это же упражнение для 6-классников: они как раз умеют составлять НОК по известному правилу.

Alibek24 в сообщении #541826 писал(а):

это не НОК!

Это именно НОК.

[Alibek24]

nnosipov в сообщении #541833 писал(а):

Alibek24 в сообщении #541762 писал(а):

2520 - самое маленькое число, которое делится без остатка на все числа от 1 до 10. Какое самое маленькое число делится нацело на все числа от 1 до 20?

Это же упражнение для 6-классников: они как раз умеют составлять НОК по известному правилу.

Alibek24 в сообщении #541826 писал(а):

это не НОК!

Это именно НОК.

В общем я был не прав, признаю;)
Решил как всегда не очень красиво, может кто подскажет как можно избежать 20-кратного написания нок???

Используется синтаксис Python

 def nod(x, y):
    if x>y:
        for j in range(1,y+1):
            if x%j==0 and y%j==0:
                m=j
    else:
        for s in range(1,x+1):
            if y%s==0 and x%s==0:
                m=s
    return m

def nok(x1, y1):
    return (x1*y1)/(nod(x1, y1))

f=0
f=nok(2,nok(3,nok(4,nok(5,nok(6,nok(7,nok(8,nok(9,nok(10,nok(11,nok(12,nok(13,nok(14,nok(15,nok(16,nok(17,nok(18,nok(19,20))))))))))))))))))
    
print f 

[EtCetera]

Alibek24

Alibek24 в сообщении #541940 писал(а):

как можно избежать 20-кратного написания нок???

Завести временную переменную и произвести нахождение искомого числа в цикле.

Однако здесь можно относительно просто обойтись без программистских ухищрений, воспользовавшись для нахождения искомого числа очевидной формулой $f(n)=\prod\limits_{p\le n}p^{\left\lfloor\log_p n\right\rfloor}$ ($p$ $\text{---}$ простое число), с помощью которой $f(20)$ можно посчитать даже на непрограммируемом калькуляторе.

[Alibek24]

EtCetera в сообщении #541985 писал(а):

Alibek24

Alibek24 в сообщении #541940 писал(а):

как можно избежать 20-кратного написания нок???

Завести временную переменную и произвести нахождение искомого числа в цикле.

Однако здесь можно относительно просто обойтись без программистских ухищрений, воспользовавшись для нахождения искомого числа очевидной формулой $f(n)=\prod\limits_{p\le n}p^{\left\lfloor\log_p n\right\rfloor}$ ($p$ $\text{---}$ простое число), с помощью которой $f(20)$ можно посчитать даже на непрограммируемом калькуляторе.

я тоже так думал, с временной переменной)))

а как это формула называется?

[Alibek24]

Ещё одна задачка!
В общем вот условие:

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

[arseniiv]

Alibek24 в сообщении #543014 писал(а):

как сделать так, что когда он делится на 2 что еще по циклу проверилось делится ли ещё раз на это простое число?

Тут уже предлагали заменять число частным от деления на исследуемое простое.

[Alibek24]

Цитата:

Тут уже предлагали заменять число частным от деления на исследуемое простое.

Ну я про это и спрашивал, вот единственное как в цикле это написать?