Problem 5
Smallest multiple
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?
最小倍数
2520是最小的能够被1到10整除的数。
最小的能够被1到20整除的正数是多少？
题目解答
朴素解法：暴力枚举（利用欧几里得算法先计算前两个数字的最小公倍数，然后用其与第三个数字计算最小公倍数，一直地推到20）
优化算法： 在本题中我们计算最小公倍数可以使用 算数基本定理
算数基本定理(拓展)：
我们通过分解每一个数字 然后维护一个素数表即可
题目代码
#include <stdio.h>
#include <math.h>
#include <inttypes.h>
int32_t prime[10] = {2,3,5,7,11,13,17,19};
int32_t book[21] = {0};
int32_t main(){for (int32_t i=2;i<=20;++i){int32_t temp = i;for (int32_t j=2;;++j){int32_t cnt = 0;if (temp % j == 0){while (temp % j == 0){++cnt;temp /= j;}if (cnt > book[j])book[j] = cnt;if(temp == 1)break;}}}int64_t ans = 1;for(int i=0;i<8;i++){ans *= pow(prime[i],book[prime[i]]);}printf("%" PRId64 "\n",ans);
}