Smallest Multiple Algorithm using Bruteforce or GCD/LCM
- 时间:2020-09-10 12:45:51
- 分类:网络文摘
- 阅读:97 次
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?
Bruteforce Algorithm to Find the Least Common Multiples
The most intuitive solution is to check number one by one and then test if it can be divisible by all the numbers from 1 to 20. A better solution is to skip 20 each time.
1 2 3 4 5 6 7 8 9 10 11 12 | function checkDivision(n) { if (n == 0) return false; for (let i = 2; i <= 20; ++ i) { if (n % i != 0) return false; } return true; } let i = 0; while (!checkDivision(i)) { i += 20; } |
function checkDivision(n) { if (n == 0) return false; for (let i = 2; i <= 20; ++ i) { if (n % i != 0) return false; } return true; } let i = 0; while (!checkDivision(i)) { i += 20; }
This takes pretty quickly to come up a solution which is 232792560
Greatest Common Divisor and Least Common Multiples
Another solution is to compute the Least Common Multiples of the numbers between 1 to 20. To compute the LCM of two numbers a, b, we need to compute the Greatest Common Divisor or both numbers.
.
We can use the iterative approach to compute the GCD.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | function gcd(a, b) { while (b != 0) { let c = a % b; a = b; b = c; } return a; } function lcm(a, b) { return a * b / gcd(a, b); } let res = 1; for (let i = 1; i <= 20; ++ i) { res = lcm(res, i); } console.log(res); |
function gcd(a, b) { while (b != 0) { let c = a % b; a = b; b = c; } return a; } function lcm(a, b) { return a * b / gcd(a, b); } let res = 1; for (let i = 1; i <= 20; ++ i) { res = lcm(res, i); } console.log(res);
–EOF (The Ultimate Computing & Technology Blog) —
推荐阅读:网站站长赚钱的七条经验分享 一道求比例尺的问题 欧拉的故事 分羊的故事 千里马的故事 监狱里的数学研究 比和比例的历史 平均数、中位数和众数的区别 黄金分割的历史 蝴蝶效应
- 评论列表
-
- 添加评论