find LCM of two numbers in cpp

Question

/Here i wrote code for find LCM of two numbers but i don't know why it is not work for 9-10 digit numbers. like if i give input as 245 and 922222222 then it is not work and don't show the output./

//code is given below

#include<iostream>
using namespace std;

long long product;

long long lcm(long long x,long long y){

    if(x>y)
        product=x;
    else
        product=y;

    while(1){
        if(product%x==0 && product%y==0){
            break;
        }
        product++;
    }

    return product;
}

int main(){
    cout<<lcm(245,922222222);
    return 0;
}

The code is formatted in such a way that at first I thought it was just random lines of gibberish. — sweenish, Sep 09 '22 at 17:44
Following on, do you know what output you should be expecting? It sounds like the program is just running for a long time. — sweenish, Sep 09 '22 at 17:47
Also, I'm almost sure that this *does* print something after waiting for eternity. — STerliakov, Sep 09 '22 at 17:47
you only need `std::gcd`, no loops, `lcm(a,b) = a*b / gcd(a,b);` — 463035818_is_not_an_ai, Sep 09 '22 at 18:10
If you're going to return `product` from your function, there's absolutely no point to it being a global variable. — Chris, Sep 09 '22 at 18:31
[What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) — Jesper Juhl, Sep 10 '22 at 02:04

score 2 · Answer 1 · answered Sep 09 '22 at 18:26

Your code is working fine, it's just going to take a few years for it to finish.

You're wasting a lot of time checking numbers that can't possibly be the result. n % (n + 1) can't possibly be 0 for any n other than 1. In general, n % (n + m) can only be 0 if m is a multiple of n. That means you can add the greater of x and y to product each loop instead of just 1 and cut down on a ton of work:

long long lcm(long long x,long long y) {

    long long greater = std::max(x, y);
    long long product = greater;

    while(product % x != 0 || product % y != 0) {
        product += greater;
    }

    return product;
}

Demo

Of course, even that is more work than you need, since std::gcd exists:

long long lcm(long long x, long long y) {
    return x / std::gcd(x, y) * y;
}

Demo

That may be violating the spirit of the assignment though.

find LCM of two numbers in cpp

1 Answers1