GCD(Greatest Common Divisor) of two numbers

Post your FreeBASIC source, examples, tips and tricks here. Please don’t post code without including an explanation.
Post Reply
ganache
Posts: 47
Joined: Aug 04, 2016 9:25

GCD(Greatest Common Divisor) of two numbers

Post by ganache »

' Program to find GCD(Greatest Common Divisor) of two numbers.

Code: Select all

declare function gcd(p As Integer, q As Integer) As Integer
Dim As Integer p, q

' recursive Euclidean algorithm
function gcd(p As Integer, q As Integer) As Integer
if q = 0 then
return p
end if
return gcd(q, p mod q)
end function

ganache
Posts: 47
Joined: Aug 04, 2016 9:25

Re: GCD(Greatest Common Divisor) of two numbers

Post by ganache »

In fact, knowing the GCD, we can also find the LCM(Least Common Multiple)
Here is a complete program that will find both GCD and LCM of two numbers.

Code: Select all


declare function gcd(p As Integer, q As Integer) As Integer
declare function lcm(p As Integer, q As Integer) As Integer
Dim As Integer p, q

' recursive Euclidean algorithm
function gcd(p As Integer, q As Integer) As Integer
if q = 0 then
return p
end if
return gcd(q, p mod q)
end function

' using gcd we can find lcm
function lcm(p As Integer, q As Integer) As Integer
return (p*q) / gcd(p, q)  ' use gcd from previous function
end function

input "Enter first integer number: ";p
input "Enter second integer number: ";q
print "GCD of the numbers is: ";gcd(p,q)
print "LCM of the numbers is: ";lcm(p,q)
Sleep

Munair
Posts: 1286
Joined: Oct 19, 2017 15:00
Location: Netherlands
Contact:

Re: GCD(Greatest Common Divisor) of two numbers

Post by Munair »

Thanks for sharing.
MrSwiss
Posts: 3910
Joined: Jun 02, 2013 9:27
Location: Switzerland

Re: GCD(Greatest Common Divisor) of two numbers

Post by MrSwiss »

The same algo, but without recursion (using a WHILE-Loop instead):
by dodicat (click me)
Post Reply