2520 is the smallest number that can be divided by each of numbers from 1 to 10 without any remainder.
What is the smallest positive number that is evenly divisible by all of the number frome 1 to 20?

分析:求能够被1到20整除的最小正整数,即求最小公倍数。相邻两位依次求最小公倍数到最后即为所求。

Python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
def lcm(n):
k = 4
multiple = 6
while k <= n:
a = multiple
b = k
while a % b != 0: #辗转相除法求最大公因子
temp = b
b = a % b
a = temp
multiple = multiple *k / b #两数相乘除最大公因子得最小公倍数
k += 1
return multiple

还有一种更加省计算量的方法,分解成一个或多个质因子相乘。设前k项的最小公倍数为m,那么

k = 2, m = 2
k = 3, m = 2*3
k = 4, m = 2*3*2
k = 5, m = 2*3*2*5
k = 6, m = 2*3*2*5
...
从中会发现质因子出现的最高次数取决于k的大小,质因子的最高次方小于等于k。
所以,可以先求出小于k的所有质数,然后计算每个质数p最高出现的次数log(k)/log(p)。(即以p为底k的log)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
import math

def f2(n):
primes = []
k = 2
while k <= n:
i = 2
flag = True
while i <= math.sqrt(k):
if k%i == 0:
flag = False
break
i += 1
if flag:
primes.append(k)
k += 1 #计算出n以内质数
a = [] #存储各个质数的最高次数
check = True
limit = math.sqrt(n) #limit的设定也是为了减少计算量,质因子的次数至少是一次,当
i = 0 #质因子大于limit时,一定是一次的
while i < len(primes):
a.append(1)
if check:
if primes[i] <= limit:
a.pop()
a.append(int(math.log(n, primes[i])) #小于等于limit时计算最高次数
else:
check = False
i += 1

i = 0
multiple = 1
for x in a:
multiple = multiple * primes[i]**x
i += 1
return multiple

参考:

最大公约数与最小公倍数- I Do Maths