Q: Given two numbers m and n, write a method to return the first number r that is

divisible by both (e.g., the least common multiple).

A:

The Approach:

What does it mean for r to be divisible by m and n? It means that all the primes in m must go into r, and all primes in n must be in r. What if m and n have primes in common?

For example, if m is divisible by 3^5 and n is divisible by 3^7, what does this mean about r? It means r must be divisible by 3^7.

The Rule: For each prime p such that p^a \ m (e.g., m is divisible by p^a) and p^b \ n, r must be divisible by p^max(a, b)

The Algorithm:

Define q to be 1.

for each prime number p less than m and n:

find the largest a and b such that p^a \ m and p^b \ n

let q = q * p^max(a, b)

return q

## Friday, September 30, 2011

Subscribe to:
Post Comments (Atom)

Military Challenge Coins

ReplyDeleteI have not seen like it so decent easy to understand thanks for sharing.

ITs you good working i like it and i also tell you something

ReplyDeleteAbout the interview

Should be looking good,, and

Thoroughly read and analyze the official job description

Be prepared to recognize and engage in various types of interviews.

Be passionate.

MBTI Hunter Valley

That is very nice sharing i like it very much.

ReplyDeleteItalian Villas for Rent

Superb question and it's answer bundles of thanks for the sharing.

ReplyDeleteVillas in Tuscany

Waooow!! Nice blog, this will be greatly helpful.

ReplyDeletemarvel golden age reading order

Your blogs stuff is purely enough for me personally.

ReplyDeletemarvel comics database