[Math] GCD & LCM

GCD(Greatest Common Divisor) & LCM(Least Common Multiple)

1. Find GCD of two number

Method 1: use basic Euclidean algorithm.
GCD(a, b) = GCD(b%a, a)
Method 2: use extended Euclidean algorithm.
GCD(a, b) = ax + by
Let values of x and y calculated by the recursive call be x1 and y1
x = y1 - ⌊b/a⌋ * x1
y = x1


2. Find LCM of two number

LCM(a, b) * GCD(a, b) = a * b

3. Reference

  • http://www.geeksforgeeks.org/mathematical-algorithms/#gcd

댓글

댓글 쓰기

이 블로그의 인기 게시물

Android essentials summary

- Binder Binder is android-specific inter-process communication mechanism and RPC mechanism. Android does not use traditional system V IPC and does use binder, which is efficient and fast. In order to provide efficient IPC, binder driver was added in linux kernel. And for app, AIDL was provided and app developers can develop binder client and server easily without coding the marshalling/unmarshalling stuffs. - ASHMEM Asynchronous shared memory was added to android linux kernel. Compared to system V shared memory, ashmem releases kernel resources when nobody refers the shared memory and kernel can reclaim unpinned shared memory when memory runs low. When app shares large amount of data to other app or service such as surface data and image, passing data by using shared memory does not need to copy data and therefore shared memory outperforms other methods like socket. - AIDL AIDL(Android Interface Definition Language) is a kind of IDL specific to android. AIDL defines programmin...
자세한 내용 보기

Useful Linux Command Line Bash Shortcuts You Should Know

Controlling The Screen Ctrl+L – clears the screen (same effect as the “clear” command). Ctrl+S – pause all command output to the screen. If you have executed a command that produces verbose, long output, use this to pause the output scrolling down the screen. Ctrl+Q – resume output to the screen after pausing it with Ctrl+S. Move Cursor on The Command Line Ctrl+A or Home – moves the cursor to the start of a line. Ctrl+E or End – moves the cursor to the end of the line. Ctrl+B or Left Arrow – moves the cursor back one character at a time. Ctrl+F or Right Arrow – moves the cursor forward one character at a time. Ctrl + Left Arrow or Alt+B or Esc and then B – moves the cursor back one word at a time. Ctrl + Right Arrow or Alt+C or Esc and then F – moves the cursor forward one word at a time. Search Through Bash History Up arrow key – retrieves the previous command. If you press it constantly, it takes you through multiple commands in history, s...
자세한 내용 보기