欧拉项目＃5;这个解决方案工作 - 但为什么？ [英] Project Euler # 5; this solution works - but why?

问题描述

项目Euler问题5表示为：2520是最小的数字，可以除以每个数字从1到10，没有任何余数。

什么是最小的正数，它是可以被所有的数字从1到20？
这是我使用的函数的c ++代码。

  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; 
} 
  

代码适用于问题中说明的示例，问题本身{ rangeLCM（10）= 2520 和 rangeLCM（20）= 232792560 }，但我认为它不完美，

除了实际计算 LCM（ans，i）两个中较大的一个（总是 ans ）可被 i 整除。如果不是，则 ans 乘以等于 i /（ans％i）或<$ c $取决于 i 是否可被（ans％i）整除的 i

这基于以下事实：

  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

然而，rangeLCM的代码为我已经尝试的所有输入提供了正确的输出，

解决方案

您的逻辑无效

  if（i％（ans％i）== 0）ans * =（i /（ans％i））; 
 else ans * = i; 
  / pre> 
 
 
例如，如果 ans = 10 和 i = 14  
 
 
原因是，在 ans 之间， / code>和 i 有共同的除数，但您的代码无法检测到。
 
 
 
实验，我写了一小段代码来使用Java来检查。
 类解决方案{
 
 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  / p> 
 
 
 lcm（a，b）的公式为
  lcm a，b）= a * b / gcd（a，b）
  
 =https://en.wikipedia.org/wiki/Greatest_common_divisor =nofollow>两个数字a和b之间的最大公约数 
 
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.

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;
    }
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.

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.

This is based on the following facts:
LCM(8,12)=24=12*(8/(12%8));

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

LCM(7,13)=91=13*7
However, it fails for the following types of cases:LCM(8,14)=56 != 8*14

Yet, the code for rangeLCM gives the right output for all inputs I have tried yet. Why? 
解决方案
Your logic does not work
          if(i%(ans%i)==0)ans*=(i/(ans%i));
          else ans*=i;
For example, if ans = 10 and i = 14, so, the lcm should be 70, but in your code, it is 140. 

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

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);
    }
}
Output
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
When i = 27, there is different between the correct answer and ans

The formula for lcm(a,b) is
lcm(a,b) = a*b/gcd(a,b)
With gcd is Greatest common divisor between two number a and b

                        
这篇关于欧拉项目＃5;这个解决方案工作 - 但为什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！