找到可以被1到20的所有數字均勻分割的最小正數？

這是一個歐拉項目挑戰，我試圖找到可以被1到20的所有數字均勻分割的最小正數？找到可以被1到20的所有數字均勻分割的最小正數？

我想出來的邏輯似乎運行得非常慢。它已經跑了最後4分鐘，仍然沒有找到數字。我試圖弄清楚a）這個邏輯是否正確？ b）爲什麼這麼長時間？和c）有人可以給我一個更有效的替代邏輯的提示。

# 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? 
smallest_num = 2520 
while smallest_num >= 2520: 
    divisor = 2 
    while smallest_num % divisor == 0 and divisor < 21: 
     print("Smalles num = {} and Divisor = {}").format(smallest_num, divisor) 
     divisor += 1 
    smallest_num += 1 
print("Smallest number is: {}").format(smallest_num)

這是仍在處理，到目前爲止，我的終端看起來像這樣

來源

2017-05-28 Burner918

此代碼將永久運行。 – ForceBru

您可以優化它，以便它不檢查1到20之間的每個數字。例如，通過檢查20，您還檢查了1,2,4,5和10. –

沒有理由爲什麼'while smallest_num> = 2520：'會永遠停止，所以不，你的邏輯是不正確的。另外你得到2520的原因是你可以首先在小問題上測試你的邏輯。嘗試編寫一個不包含2520的程序，但在考慮從1到10的數字時產生2520作爲輸出。 –

這是你的方法運行「正常」（使用期限不受限制），但@詹姆斯提到將採取作爲循環的時間非常多。

divisors = np.arange(1, 21) 
num = 2520 
while True: 
    if np.all(num % divisors == 0): 
     print(num) 
     break 
    num += 1

一個更好的方法（對於Python 3.x）。直接從類似question：

import functools 
import math 

functools.reduce(lambda x,y: x*y//math.gcd(x, y), range(1, 21)) 
Out[27]: 232792560

來源

2017-05-28 15:22:14

我不是100％肯定，如果我的解決方案是真正正確的，但我想這是，這是非常快的。

首先，我們不需要關心所有的因數，因爲大多數是彼此的倍數。所以最好的方法是倒數數字，例如從20開始減少到1.

我看了一下素數，解決方案需要是10以上所有素數的倍數，此外我們需要檢查除數20，其餘的可以忽略不計，因爲在測試除數18時，9也會起作用，等等。

所以我mulitplied 11 * 13 * 17 * 19 * 20所得的是923780，是由除盡至少素數+ 20

因此，我將在923780和測試僅每第九十二萬三千七百八十零數字開頭。

smallest_num = 923780 
steps = 923780 
while True: 
    divisor = 19 
    while smallest_num % divisor == 0 and divisor > 10: 
     print("Smalles num = {} and Divisor = {}").format(smallest_num, divisor) 
     divisor -= 1 
    if divisor == 10: 
     print("Smallest number is: {}").format(smallest_num) 
     break 
    smallest_num += steps

也許我有邏輯錯誤？！

來源

2017-05-28 15:43:49 olisch

以下代碼正常工作。

#!/usr/bin/env python 
import math 

#Generating primes 
divisorMax = 20; 

top = divisorMax + 1 #divisor max is the upper limit 

p = [x for x in range(2,top)] 

for num in p: 
    for idx in range(2,(top//num)+1): 
    if num*idx in p: 
     p.remove(num*idx) 

#Solving the problem 
result = 1; 

for i in range(0, len(p)): 
    a = math.floor(math.log(divisorMax)/math.log(p[i])); 
    result = result * (p[i]**a); 

print(result)

您正在使用蠻力技術計算的數量，這是很容易理解和編寫，但需要很多時間。

我正在使用Prime Factorisation技術解釋here。

來源

2017-05-28 16:34:44

找到可以被1到20的所有數字均勻分割的最小正數？

回答

相關問題