what is the most efficient way to calculate the least common multiple of two integers

I just came up with this, it definitely leaves something to be desired

```
int n = 7, m = 4, n1=n, m1=m;
while (m1 != n1) {
if (m1 > n1)n1 += n;
else m1 += m;
}
System.out.println("lcm is " + m1);
```

Take successive multiples of the larger of the two numbers until the result is a multiple of the smaller.

this might work..

```
public int LCM(int x, int y)
{
int larger = x>y? x: y,
smaller = x>y? y: x,
candidate = larger ;
while (candidate % smaller != 0) candidate += larger ;
return candidate;
}
```

The least common multiple of a and b is the product divided by the greatest common divisor. I.e. lcm(a, b) = ab/gcd(a, b). So the question becomes how to find the gcd. The Euclidean algorithm is generally how the gcd is computed. The direct implementation of the classic algorithm is efficient, but there are variations that take advantage of binary arithmetic to do a little better. See Knuth TAOCP volume 2, Seminumerical Algorithms.

I think that the approach of "reduction by the greatest common divider" should be faster. Start by calculating the GCD (e.g. using Euclid's algorithm), then divide the product of the two numbers by the GCD.

**Remember The least common multiple is the least whole number that is a multiple of each of two or more numbers.**

If you ae trying to figure out the LCM of three integers, follow these steps:

```
**Find the LCM of 19, 21, and 42.**
```

Write the prime factorization for each number. 19 is a prime number. You do not need to factor 19.

21 = 3 × 7 42 = 2 × 3 × 7 19

Repeat each prime factor the greatest number of times it appears in any of the prime factorizations above.

2 × 3 × 7 × 19 = 798

The least common multiple of 21, 42, and 19 is 798.

First of all, you have to find the greatest common divisor

```
for(int = 1; i <= a && i <= b; i++) {
if (i % a == 0 && i % b == 0)
{
gcm = i;
}
}
```

After that, using the GCM you can easily find the least common multiple like this

```
lcm = a / gcm * b;
```

I don't know whether it is optimized or not, but probably the easiest one:

```
public void lcm(int a, int b)
{
if (a > b)
{
min = b;
max = a;
}
else
{
min = a;
max = b;
}
for (i = 1; i < max; i++)
{
if ((min*i)%max == 0)
{
res = min*i;
break;
}
}
Console.Write("{0}", res);
}
```

Best solution in C++ below without overflowing

```
#include <iostream>
using namespace std;
long long gcd(long long int a, long long int b){
if(b==0)
return a;
return gcd(b,a%b);
}
long long lcm(long long a,long long b){
if(a>b)
return (a/gcd(a,b))*b;
else
return (b/gcd(a,b))*a;
}
int main()
{
long long int a ,b ;
cin>>a>>b;
cout<<lcm(a,b)<<endl;
return 0;
}
```

C++ template. Compile time

```
#include <iostream>
const int lhs = 8, rhs = 12;
template<int n, int mod_lhs=n % lhs, int mod_rhs=n % rhs> struct calc {
calc() { }
};
template<int n> struct calc<n, 0, 0> {
calc() { std::cout << n << std::endl; }
};
template<int n, int mod_rhs> struct calc<n, 0, mod_rhs> {
calc() { }
};
template<int n, int mod_lhs> struct calc <n, mod_lhs, 0> {
calc() { }
};
template<int n> struct lcm {
lcm() {
lcm<n-1>();
calc<n>();
}
};
template<> struct lcm<0> {
lcm() {}
};
int main() {
lcm<lhs * rhs>();
}
```

Similar Questions

I have a fairly large dataset and a query that requires two joins, so efficiency of the query is very important to me. I need to retrieve 3 random rows from the database that meet a condition based on

I am working on a jQuery Mobile Web App where a company will have the ability to message certain groups of users (based on their profile preferences). I am debating on what is the most efficient way t

I'm looking for a fast and efficient way to retreive 2 strings from multiple xml files. The files them selves aren't that big only 50kb to 100kb and the number of files can range from none to 100. I'v

What is the most efficient way to get an array of months, from a specified date, up until the present day, grouped by year. Eg getMonths(August 2012) would output array( array(Year=>2013, mo

I'm trying to make an Euler problem: for now my speed-defining step is counting the least common multiple of two numbers. So, which one of these methods is faster? Why? public static int lcm(int a, i

I'm trying to compare two lists of integers, each the same size, in Python 2.6. The comparison I need is to compare the first item in List 1 with the first item in List 2, the second item in List 1 wi

Say my url is www.example.com/usa/california/redding/ What is the most efficient way to return the following: $urls = array ( 0 => '/usa/', 1 => '/usa/california/', 2 => '/usa/california/redd

Given two inclusive integer ranges [x1:x2] and [y1:y2], where x1 <= x2 and y1 <= y2, what is the most efficient way to test whether there is any overlap of the two ranges? A simple implementatio

For example, let's take the format of a forum, where we have multiple users and multiple threads. Say this forum wants to track which users have read which threads and, say, use that information to ma

Question: I want code for: syntax highlighting (of programming languages) Language: C# or assembly x86 (preferably C#) Platform: Windows Qualifications: most efficient implementation possible / most p

I'd like to ask what is the most efficient (and fastest) way to search for data between 2 dates? Let's consider having following simple query: SELECT Date_,counter1,counter2,... WHERE (date range cond

What's the best and most efficient book to learn JavaScript?

I have a string object in c# with a bunch of elements delimited by '/' characters. The string will look something like this: element1/element2/element3/element4 What's the most efficient way to chan

I have a database which consists of 5 columns Each column is an INT I want to find out which numbers occur most frequently in each column I also wanted to know which sequence of numbers occurs more

Suppose I want to sequentially access all the elements in a C++ container, which way is the most efficient one? I illustrated my question in the following example: std::vector<int> abc; abc.push

I've seen a lot of discussion on SO related to rounding float values, but no solid Q&A considering the efficiency aspect. So here it is: What is the most efficient (but correct) way to round a fl

What is the most efficient way to insert one Vector into another at specific position? For example: var aa:Vector.<int> = Vector.<int>([1, 2, 3]); var bb:Vector.<int> = Vector.<in

I need to calculate distances between every pair of points in an array and only want to do that once per pair. Is what I've come up with efficient enough or is there a better way? Here's an example, a

I have a table of posts and comments. Posts and comments have a post_id, but comments also have a parent_id that refers to another post in the same table. I'm trying to find the most efficient way

Seeing that the POCO template out-of-the-box does not include OnPropertyChanged support for simplicity, what would be the neatest [and most efficient] way to implement property changed events to my PO

I am working on a project which has to store tens and thousands of images on a server and let the users access them. I need the most efficient method to store these images and to retrieve them. Also,

Just wondered if anyone could point me in the right direction of storing multiple attributes and their values in SQL? Say I've got like First Name, Last Name, Company, Twitter, Facebook etc etc. with

I have a string, and I want to check whether it begins with a certain character (# in this case). I'd like to know the most efficient way of doing this! What I'm thinking of is if {[string compare -le

Possible Duplicate: What is the fastest way to swap values in C? I need to exchange values of two integers (for example x and y) This is the simplest way: int temp = x; x = y; y = temp; and I also

What is the most efficient way to organise the following pandas Dataframe: data = Position Letter 1 a 2 b 3 c 4 d 5 e into a dictionary like alphabet[1 : 'a', 2 : 'b', 3 : 'c', 4 : 'd', 5 : 'e']?

In igraph, what's the least cpu-expensive way to find: the two most remote vertices (in term of shortest distances form one another) of a graph. Unlike the farthest.points() function, which chooses t

*Efficient here basically means in terms of smaller size (to reduce the IO waiting time), and speedy retrieval/deserialization times. Storing times are not as important. I have to store a couple of

What is an efficient way to find the most common element in a Python list? My list items may not be hashable so can't use a dictionary. Also in case of draws the item with the lowest index should be r

I have to achieve the following layout in one of my android applications: Edit: I also need the selection of one of the elements to be displayed in a similar way as that: So each of the 3 elements h

In ruby, what is the most efficient way to calculate the bit difference between two unsigned integers (e.g. the hamming distance)? Eg, I have integer a = 2323409845 and b = 1782647144. Their binary r

I'm working on an app where I'm validating the users input against a 5000 line list. - i.e. matching the name entered exists in the list. Whats the most efficient and quickest way to do this - should

I'm looking to find the simplest way to return the most common value in multiple column results of a select statement that is grouped. Everything I am finding online points to RANK on a single item in

What is the most efficient way to create a column of vectors in a data.table where we need to match elements from a second data.table. For example, given the two data.tables below > A_ids.DT >

How do you calculate the least common multiple of multiple numbers? So far I've only been able to calculate it between two numbers. But have no idea how to expand it to calculate 3 or more numbers. So

What is the most efficient way in doing file operations in PHP, Add / Edit / Delete files and Directory using PHP. I have created a file manager using CI's FTP Class, i just want to know if what i a

I'm looking for the most effecient way to resolve a given url to its final end point, following all 30x redirects and location headers. Basically, I have a bunch of URLs like http://foo.com that when

I have four different types of objects within my environment(box2d), each type of object having multiple instances of itself, and would like to find the most efficient way to deal with adding and mani

Using C# what is the most reliable way to calculate network bandwidth speed? I've found a few examples using NetworkInterface, Performance Counters, native Win32 code, etc. but they all provide differ

What's the most efficient way to select multiple entities by primary key? public IEnumerable<Models.Image> GetImagesById(IEnumerable<int> ids) { //return ids.Select(id => Images.Find(id

We have few node.js processes that should be able to pass messages, What's the most efficient way doing that? How about using node_redis pub/sub EDIT: the processes might run on different machines

What is the best way to concatenate two integers to an integer in Fortran? integer a = 999 integer b = 1111 integer c should be 9991111 Thanks, SM.

Pretty simple scenario. I have a web service that receives a byte array that is to be saved as a particular file type on disk. What is the most efficient way to do this in C#?

What is an efficient way to implement a multiple file client upload service? Are there any popular libraries for that? Basically I'm looking at a Web view, served a client, that would allow them to up

I'm using the following code (repeated) to redirect 6 additional TLDs to one primary TLD. is there a more efficient way to achieve the same result? RewriteEngine on RewriteCond %{HTTP_HOST} !^(www\.)?

What is the most memory efficient way to loop through an NSMutableArray of custom objects? I need to check a value in each object in the array and return how many of that type of object is in the arra

If I have a CSS class which I only ever apply to form elements, eg: <form class=myForm> Which of these two jQuery selectors is most efficient, and why? a) $('form.myForm') b) $('.myForm')

What is the quickest way to get a large amount of data (think golf) and the most efficient (think performance) to get a large amount of data from a MySQL database to a session without having to contin

function returnsAnArray () { return array ('test'); } echo returnsAnArray ()[0]; generates a syntax error in PHP. What's the most efficient way to directly obtain an element from a returned array wit

I have a spreadsheet that has data like this Group,Region,Market G7,EMEA,Germany G7,NA,Canada G7,APAC,Japan What is the most efficient way to capture this information? I use a dictionary to store thi

Which of these methods are the most efficient one or is there a better way to do it? this.returnList[i].Title[0].ToString() or this.returnList[i].Title.Substring(0, 1)