_05a_gcd Namespace Reference

Euclid' (300 BC) GCD algorithm. More...

Classes
class	Usage
	Exception class. More...

Functions
def	gcdr (a, b)
	GCD (Greatest Common Divisor) of two integers. More...
def	gcdi (a, b)
	GCD (Greatest Common Divisor) of two integers. More...
def	gcdf (x, y)
	GCD (Greatest Common Divisor) of two integers. More...
def	lcm (x, y)
	Least Common Multiple, which returns the smallest number that can be divided by x and y without any remainder. More...
def	main (argv=None)
	main function for testing. More...

Detailed Description

Euclid' (300 BC) GCD algorithm.

Author

Paulo Roma

Since

10/12/2006

See also

http://en.wikipedia.org/wiki/Euclidean_algorithm

Function Documentation

gcdf()

def _05a_gcd.gcdf	(		x,
			y
	)

GCD (Greatest Common Divisor) of two integers.

This is a fast algorithm.

Parameters

x	first positive integer.
y	second positive integer.

Returns

GCD of a and b.

Referenced by lcm(), and main().

gcdi()

def _05a_gcd.gcdi	(		a,
			b
	)

GCD (Greatest Common Divisor) of two integers.

This is an iterative algorithm.

Parameters

a	first positive integer.
b	second positive integer.

Returns

GCD of a and b.

gcdr()

def _05a_gcd.gcdr	(		a,
			b
	)

GCD (Greatest Common Divisor) of two integers.

This is a recursive algorithm (tail recursion).

Parameters

a	first positive integer.
b	second positive integer.

Returns

GCD of a and b.

lcm()

def _05a_gcd.lcm	(		x,
			y
	)

Least Common Multiple, which returns the smallest number that can be divided by x and y without any remainder.

Parameters

x	first integer.
y	second integer.

Returns

LCM.

See also

https://en.wikipedia.org/wiki/Least_common_multiple

https://www.w3resource.com/python-exercises/challenges/1/python-challenges-1-exercise-37.php

References gcdf().

Referenced by main().

main()

def _05a_gcd.main

(

argv = None

)

main function for testing.

Parameters

argv

None

References gcdf(), _01d_dec2bin.input, and lcm().