Skip to main content

Least common multiple

SA I write this post because I failed yesterday to solve the topcoder TCO 250 problem , it was about find the LCM -Least Common multiple -simply it is smallest number which accept the division on -non zero- numbers .

how we calculate it? there exist two ways lets discuss both:
for example 3,4,6
first way find the multiple of all numbers 2,3,4...etc.
Multiples of 2: 4,6,8,10,12,14,16.
Multiples of 3: 6,9,12,15.
Multiples of 4: 8,12,16,20.

as you see 12 is the smallest common number which appear on all numbers .

second way factor each number into it prime component and do the following steps :
1-Count the number of times each prime number appears in each of the factorizations.

2-For each prime number, take the largest of these counts.

3-Write down that prime number as many times as you counted for it in step 2.

4-The least common multiple is the product of all the prime numbers written down.

example 5,6,15.

Factor into primes

Prime factorization of 5 is 5

Prime factorization of 6 is 2 x 3

Prime factorization of 15 is 3 x 5

Notice that the different primes are 2, 3 and 5.

Now, we do Step #1 - Count the number of times each prime number appears in each of the factorizations...

The count of primes in 5 is one 5

The count of primes in 6 is one 2 and one 3

The count of primes in 15 is one 3 and one 5.

Step #2 - For each prime number, take the largest of these counts. So we have...

The largest count of 2s is one

The largest count of 3s is one

The largest count of 5s is one

Step #3 - Since we now know the count of each prime number, you simply - write down that prime number as many times as you counted for it in step 2.

Here they are...

2, 3, 5

Step #4 - The least common multiple is the product of all the prime numbers written down.

2 x 3 x 5 = 30

Therefore, the least common multiple of 5, 6 and 15 is 30.

So there you have it. A quick and easy method for finding least common multiples.

reference see the Link

Comments

Post a Comment

Popular posts from this blog

DevExpress C# Chart Tutorial

Hello , this blog post about Charting in DevExpress , I faced many problems I visited hundreds of pages to solve this problems , actually it was the first time I use DevExpress Charts, Work is not like school or university , in school if you don't know thing you can learn it any time you want , in work you have to do today task yesterday, I like to share my knowledge and skills with you , I hope this Post help you . // clear series on chart  chart.Series.Clear(); // clear Titles of chart chart.Titles.Clear(); // legend alignment  chart.Legend.AlignmentHorizontal = LegendAlignmentHorizontal.Center; chart.Legend.AlignmentVertical = LegendAlignmentVertical.Bottom; chart.Legend.Direction = LegendDirection.LeftToRight; // creating series // series view Type example Line DevExpress.XtraCharts.Series series = new DevExpress.XtraCharts.Series("series name ", ViewType.Line); // add title  DevExpress.XtraCharts.ChartTitle chtTitle = new DevExpress.XtraCharts.Cha...
3 comments
Read more

LeetCode Problem #11 Container With Most Water

LeetCode Problem #11 Container With Most Water Given  n  non-negative integers  a 1 ,  a 2 , ...,  a n  , where each represents a point at coordinate ( i ,  a i ).  n  vertical lines are drawn such that the two endpoints of line  i  is at ( i ,  a i ) and ( i , 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water. Note:  You may not slant the container and  n  is at least 2. The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49. Problem Link Solution Number One O(n^2) Brute Force : Try all valid combinations  outer loop start from i = 0 to length of array inner loop start from j = i+1 to length of array  compare current area with new area and choose max. return max area. Solution Number Two O(n) : Linear Solution greedy algorithm: calc...
Post a Comment
Read more

Recursion

Recursion is a programming technique which function calls itself , this seems strange , however it is one of the most interested and effective technique in programming. it helps you write code in less statements and provides unique conceptual frame work to solve problems. lets discus some problems to know how it works : first example Triangular Numbers : it is series like : 1,3,6,10,15,21........ etc our program should get the nth term in the series, the numbers in this series called triangular numbers due to they can be visualized as a triangle. triangular numbers fig 1 finding the nth term using a loop see this figure : loop adding 1+2+3+4 and so on code is easy  , a loop will add numbers from n to 0 like this int triangle(int n) { int total = 0; while(n > 0) // until n is 1 { total = total + n; // add n (column height) to total --n; // decrement column height } return total; } it easy enough and for sure it is fast . before we start the recu...
2 comments
Read more