求能够被1-20中任意一个数整除的最小正整数
/**
* 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?
*/
代码：
private static long smallMul(int N) {
long r = N;
for (int i = 2; i < N; i++) {
r = r * i / gys(r, i);
}
return r;
}
private static long gys(long m, long n) {
long tmp = m % n;
while (tmp != 0) {
m = n;
n = tmp;
tmp = m % n;
}
return n;
}
public static void main(String[] args) {
System.out.println(iSmallMul(20));
}
思想：
1、这个正整数其实就是1-20的最小公倍数，而多个数的公倍数可以分开求，即a、b、c的公倍数求法可以是先求a、b的公倍数d，然后再求d、b的公倍数
2、最小公倍数求法为两者积除以两者最大公约数
3、公约数求法是经典的求法
4、参考答案是维护一个素数表，然后使用素数表相乘，详情见官网参考答案