Project Euler 5 в Python - Как я могу оптимизировать свое решение?

Question

Я недавно работал над проблемами Project Euler в Python.Я довольно новичок в Python, и все еще несколько новичок в качестве программиста.

В любом случае, я столкнулся с проблемой скорости, кодирующей решение проблемы № 5.Проблема в том, что

"2520 - это наименьшее число, которое можно разделить на каждое из чисел от 1 до 10 без остатка. Наименьшее положительное число, которое равномерно делится на все числа от 1to 20? "

Я проверил некоторые из них и не смог найти ничего по этой проблеме, относящейся к Python специально.Было несколько завершенных сценариев, но я хочу избегать полного просмотра кода другого, по возможности вместо того, чтобы улучшать свой собственный.

Написанный мною код успешно работает на примере 2520 и в диапазоне от 1 до 10, и его следует изменять напрямую для работы с вопросом.Однако, запустив его, я не получаю ответ.Предположительно, это очень большое число, а код недостаточно быстрый.Печать текущего проверяемого числа, кажется, поддерживает это, достигая нескольких миллионов без ответа.

Код в его текущей реализации выглядит следующим образом:

rangemax = 20
def div_check(n):
    for i in xrange(11,rangemax+1):
        if n % i == 0:
            continue
        else:
            return False
    return True

if __name__ == '__main__':
   num = 2
   while not div_check(num):
       print num
       num += 2
   print num

Я уже сделалпара изменений, которые, я думаю, должны помочь скорости.Во-первых, для того, чтобы число делилось на все числа от 1 до 20, оно должно быть четным, поскольку только четные числа делятся на 2. Следовательно, я могу увеличивать на 2 вместо 1. Кроме того, хотя я и не думал оЯ сам нашел, что кто-то указал, что число, делимое на 11 - 20, делится на 1 - 10. (Не проверял это число, но кажется разумным)

Код все еще, однако, не быстрыйдовольно.Какие оптимизации, программные или математические, я могу сделать, чтобы этот код работал быстрее?

Заранее спасибо всем, кто может помочь.

Answer 1

Вот мое решение на Python, оно имеет 12 итераций, поэтому скомпилировано довольно быстро:

smallest_num = 1
for i in range (1,21):
    if smallest_num % i > 0: # If the number is not divisible by i
        for k in range (1,21):
            if (smallest_num * k) % i == 0: # Find the smallest number divisible by i    
                smallest_num = smallest_num * k
                break
print (smallest_num)

Answer 2

Здесь я также использовал простой способ факторизации.

#!/usr/bin/env python
import math
def is_prime(num):
    if num > 1:
        if num == 2:
            return True
        if num%2 == 0:
            return False
        for i in range(3, int(math.sqrt(num))+1, 2):
            if num%i == 0:
                return False
        return True
    return False

def lcm(number):
    prime = []
    lcm_value = 1
    for i in range(2,number+1):
        if is_prime(i):
            prime.append(i)
    final_value = []
    for i in prime:
        x = 1
        while i**x < number:
            x = x + 1
        final_value.append(i**(x-1))
    for j in final_value:
        lcm_value = j * lcm_value
    return lcm_value

if __name__ == '__main__':
    print lcm(20)

После проверки того, сколько времени это заняло, все было совсем неплохо.

root @ l-g6z6152: ~ / learn / project_euler # time python lcm.py

232792560

real    0m0.019s
user    0m0.008s
sys 0m0.004s

Answer 3

Я думаю, что это ответ:

primes = [11, 13, 17, 19]
result = 2520

for i in primes:
    result *= i

print (result * 2)

Answer 4

import time
primes = [11,13,17,19]
composites = [12,14,15,16,18,20]

def evenlyDivisible(target):
    evenly = True
    for n in composites:
        if target % n > 0:
            evenly = False
            break
return evenly

step = 1
for p in primes:
    step *= p

end = False
number = 0
t1 = time.time()
while not end:
    number += step
    if evenlyDivisible(number):
        end = True
        print("Smallest positive evenly divisible number is",number)
t2 = time.time()
print("Time taken =",t2-t1)

Выполнено за 0,06 секунды

Answer 5

Вариант машинописного текста, который кажется относительно быстрым, используя рекурсию и известные факты.

Answer 6

Здесь программа на языке Си. Приветствия

#include <stdio.h>
#include <stdlib.h>
//2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
//What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?
bez_ost(int q)
{
    register br=0;
    for( register i=1;i<=20;i++)
    if(q%i==0)
    br++;

    if(br==20)
    return 1;
    return 0;
}

int main()
{
   register j=20;
   register ind=0;

   while(ind!=1)
   {
       j++;
       if(bez_ost(j))
       break;
   }
   fprintf(stdout,"\nSmallest positive number that is evenlu divisible by all of the numbers from 1 to 20 is: %d\n\a",j);
   system("Pause");

}

Answer 7

up = int(input('Upper limit: '))
number = list(range(1, up + 1))
n = 1

for i in range(1, up):
    n = n * number[i]
    for j in range(i):
        if number[i] % number[j] == 0:
            n = n / number[j]
            number[i] = number[i] / number[j]
print(n)

Answer 8

У меня была такая же проблема. Алгоритм кажется довольно медленным, но, тем не менее, он работает.

result = list()
xyz = [x for x in range(11, 21)]
number = [2520]
count = 0
while len(result) == 0:
    for n in number:
        print n
        for x in xyz:
            if n % x == 0:
                count += 1
            elif n % x != 0:
                count = 0
                break
    if count == 10:
        result.append(number[0])
    elif count != 10:
        number[0] += 1

print result 

Это был алгоритм, который я сделал.

Answer 9

Как я могу уменьшить сложность этого

num = 1
found = False
while not found:
    count =0
    for i in range(1, 21):
        if num %i == 0:
            count+=1
    if count ==10:
        print(num)
        found = True
    num+=1

Answer 10

Как насчет этого?В конце концов, требуемое число - это LCM заданных чисел.

def lcm(a,b):
lcm1 = 0
if a == b:
    lcm1 = a
else:
    if a > b:
        greater = a
    else:
        greater = b
    while True:
        if greater % a == 0 and greater % b == 0:
            lcm1 = greater
            break
        greater += 1

return lcm1            


import time
start_time = time.time()

list_numbers = list(range(2,21))

lcm1 = lcm(list_numbers[0],list_numbers[1])

for i in range(2,len(list_numbers)):
    lcm1 = lcm(lcm1,list_numbers[i])

print(lcm1)
print('%0.5f'%(time.time()-start_time))

Этот код занял целых 45 секунд, чтобы получить ответ на конкретный вопрос!Надеюсь, это поможет.