Smallest Multiple Algorithm using Bruteforce or GCD/LCM

  • 时间:2020-09-10 12:45:51
  • 分类:网络文摘
  • 阅读:100 次

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.

tex_76d14b2469e9f8f27e584f068091608a Smallest Multiple Algorithm using Bruteforce or GCD/LCM algorithms javascript math project euler .

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) —

推荐阅读:
5 Growth Steps to a Profitable Blog  5 Vital Tips for Starting an Awesome Travel Blog  Smart Tips for Travel Bloggers  How to Create Content for a Narrow Niche  5 SEO Tips Every New Blogger Should Keep in Mind  5 Inspiring Blog Design Examples that Improved Readership  How to Check If Two Strings are Buddy Strings?  Innovative Plugins You Need On Your Mobile Business Site  Why Having a Phone Service is a Must for Businesses?  How to Validate a Perfect Number (Integer)? 
评论列表
添加评论