CODEWITHSUNDEEP
c++algorithm
glear14195
glear14195

Reputation: 80

Project Euler # 5; this solution works - but why?

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?

Upvotes: 0

Views: 304

Answers (2)

Pham Trung
Pham Trung

Reputation: 11284

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

Upvotes: 4

user4708940
user4708940

Reputation:

I think you are missing a lot of cases you have to implement the Euclidean algorithm at 

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

Upvotes: 0

Related Questions