Smallest Multiple

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

文章目录