项目欧拉问题5被表述为：2520是最小的数目可以由每个号码被划分为1〜10，没有任何剩余

The project Euler problem 5 is stated as : "2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

这是最小正数，它是由所有号码从1至20整除？ 这里的C ++ $ C $下我使用的功能。

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?" Here's the c++ code for the function I'm using.

    long long unsigned int rangeLCM(int n)
    {
         long long unsigned int ans=1;
         for(int i=1;i<=n;i++)
         {
            if(ans%i!=0)
            {
              if(i%(ans%i)==0)ans*=(i/(ans%i));
              else ans*=i;
            }
         } 
         return ans;
    }

在code很适合在这个问题，问题本身{ rangeLCM（10）= 2520 和 rangeLCM（陈述的例子20）= 232792560 }，但我认为它并不是完美的，并错过了一些边缘情况。

The code works well for the example stated in the problem and the problem itself{rangeLCM(10)=2520 and rangeLCM(20)=232792560}, but I think it's not perfect and is missing out on some edge cases.

而不是实际计算 LCM（ANS，我），我已签了两个（总 ANS ）是整除我。如果没有，那么 ANS 乘以数量等于 I /（ANS％I）或我取决于是否我是（ANS％I）或不

Instead of actually calculating the LCM(ans,i), I have checked that the bigger of the two(always ans) is divisible by i. If not, then ans is multiplied by a number equal to i/(ans%i) or i depending on whether i is divisible by (ans%i) or not.

这是基于以下事实：

LCM(8,12)=24=12*(8/(12%8));

LCM(9,30)=90=30*(9/(30%9)

LCM(7,13)=91=13*7

然而，失败的案件有以下几种： LCM（8,14）= 56 = 8 * 14

然而，$ C $下rangeLCM给出正确的输出，我已经尝试过所有的输入。为什么？

Yet, the code for rangeLCM gives the right output for all inputs I have tried yet. Why?

推荐答案

您逻辑不工作

          if(i%(ans%i)==0)ans*=(i/(ans%i));
          else ans*=i;

例如，如果 ANS = 10 和 I = 14 ，所以，在LCM应该是70，但在code，它是140。

For example, if ans = 10 and i = 14, so, the lcm should be 70, but in your code, it is 140.

原因是，在 ANS 和我，也有共同的除数，但你的code不能检测。

The reason is, between ans and i , there are common divisors, but your code cannot detect that.

有关的实验，我已经写了一小块code检查使用Java。

For experiment, I have written a small piece of code to check using Java.

class Solution {

    public static void main(String[] args) {
        long ans = 1;
        for (long i = 1; i <= 40; i++) {
            if (ans % i != 0) {

                long before = (ans*i/gcd(ans,i));
                if (i % (ans % i) == 0){
                    ans *= (i / (ans % i));
                }else{
                    ans *= i;
                }
                System.out.println(ans + " " + before + " " + i);
            }
        }
    }

    public static long gcd(long a, long b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }
}

输出

2 2 2
6 6 3
12 12 4
60 60 5
420 420 7
840 840 8
2520 2520 9
27720 27720 11
360360 360360 13
720720 720720 16
12252240 12252240 17
232792560 232792560 19
5354228880 5354228880 23
26771144400 26771144400 25
722820898800 80313433200 27
20961806065200 20961806065200 29
649815988021200 649815988021200 31
1299631976042400 1299631976042400 32
48086383113568800 48086383113568800 37

当I = 27，也就是正确答案之间和不同 ANS

When i = 27, there is different between the correct answer and ans

的公式为LCM（A，B）是

The formula for lcm(a,b) is

lcm(a,b) = a*b/gcd(a,b)

使用GCD是最大公约数之间的两个数a和b

With gcd is Greatest common divisor between two number a and b