how can I FIND hcf and lcm of number with time complexity O(log n ) by using vectors

Question

In this program,we need to find hcf and lcm of a number and must use vector for it and time complexity should be O(log n) and using c++.

class Solution 
{
  public:
    
    vector<long long> lcmAndGcd(long long A , long long B)
    {
         
        long long min,hcf,lcm;
        // code here
        if(A<B)
        min=A;
        else
        min=B;
        for(long long i=min;i>=1;i--)
        {
            if((A%i==0)&&(B%i==0))
            {
             hcf=i;
            
             break;
            }
        }
        lcm=(A*B)/hcf;
        vector<long long> v;
         v.push_back(lcm);
       v.push_back(hcf);
       
        return v;
    }
    
};

I did this but I am not able to do it with time complexity O(logN)

Answer 1

The C++17 standard library provides std::gcd and std::lcm. I strongly advise against implementing them yourself. This leads to slow, error-prone and unnecessarily complicated code.

#include <cstdint>
#include <iostream>
#include <numeric>
#include <vector>

std::vector<std::int64_t> lcm_and_gcd(std::int64_t const a, std::int64_t const b) {
    return {std::lcm(a, b), std::gcd(a, b)};
}

int main() {
    auto const data = lcm_and_gcd(25, 30);
    std::cout << "lcm(25, 30) = " << data[0] << '\n';
    std::cout << "gcd(25, 30) = " << data[1] << '\n';
}