"""5. 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?"""
list=[]
possibility_list=[]
base=1
numberlist=[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20]
for number in numberlist:
for iteration in range(1000):
list.append(iteration*number)
for possibility in list:
if list.count(possibility)==20:
print("Found LCM of [1:21] -->", str(possibility))
possibility_list.append(possibility)
else: continue
print(min(possibility_list))
我目前正在嘗試解決歐拉問題 #5，它想找到數字 1-20 的 LCM。上面的代碼是蠻力，但由于某種原因它不起作用。有人可以指出我正確的方向嗎？
uj5u.com熱心網友回復：
從 python 3.9 開始，您可以直接計算最小公倍數：
from math import lcm
print(lcm(*range(1, 11)))
如果那是“作弊”，請從這樣的回圈開始：
from math import lcm
result = 1
for i in range (1, 11):
result = lcm(result, i)
然后替換lcm為gcd. gcd（最大公約數）的兩個引數版本自 python 3.5 以來就已經存在：
from math import gcd
result = 1
for i in range (1, 11):
result *= i // gcd(result, i)
現在gcd是使用 Euclid 演算法相對容易實作的東西。我們的想法是，如果兩個數字的GCDx和y是g，然后x = a * g和y = b * g，用a，b比較素。如果a和b不是素數，你可以將它們除以它們的公倍數并乘以g那個數量。讓我們說a >= b。如果x是的倍數y，b必須為1（再次，a和b互質），因此y = g。否則，c = a - b必須是互質既a與b（否則他們都擁有一個共同的因素）。因此，我們可以對y和重復相同的推理z = x - y直到兩個數變成彼此的倍數。序列必須收斂，因為數字隨著每次減法而減少：
def gcd(x, y):
if x < y:
x, y = y, x
if x % y == 0:
return y
return gcd(x - y, y)
result = 1
for i in range (1, 11):
result *= i // gcd(result, i)
您可能可以使這更有效，但這應該足以形成對如何解決問題的理解。
在一般情況下，非遞回 GCD 可能是可取的，因為 python 支持任意大小的整數。你可以將它實作為
def gcd(x, y):
while True:
if x < y:
x, y = y, x
if x % y == 0:
return y
x -= y
即使你要使用蠻力，我建議你用更多的智慧來做。例如，您知道10 < lcm <= 1 * 2 * ... * 9 * 10您可以這樣寫支票：
numbers = range(1, 11)
product = 1
for i in numbers:
product *= i
for n in range(max(numbers) 1, product 1):
for i in numbers:
if n % i != 0:
break
else:
break
print(n)
內回圈針對所有numbers. 如果回圈終止而沒有中斷，n則是所有數字的倍數。這會觸發else子句，它跳出外部回圈。結果保證是正確的，因為如果沒有中斷回圈，n將是所有數字的倍數。
在上述所有情況下，包含范圍 [1, 20] 代替 [1, 10] 是微不足道的。
uj5u.com熱心網友回復：
numberlist = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
def is_prime(num: int) -> bool:
for factor in range(2, num):
if num % factor == 0:
return False
return True
prime_list = list(filter(is_prime, numberlist))
additional_factor_prime = []
for number in numberlist:
temp_factor_list = [*prime_list] additional_factor_prime
temp_number = number
for index in range(len(temp_factor_list) - 1, -1, -1):
if temp_number in prime_list:
break
cur_factor = temp_factor_list[index]
if temp_number % cur_factor == 0:
temp_factor_list.pop(index)
temp_number //= cur_factor
if temp_number not in temp_factor_list and temp_number != 0 and temp_number != 1:
additional_factor_prime.append(temp_number)
factor_list = [*prime_list] additional_factor_prime
LCM = 1
for number in factor_list:
LCM *= number
print(LCM)
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/402045.html