# SS64 Forum

You are not logged in.

## #1 05 Nov 2016 13:54

Batcher
Member
Registered: 20 Jul 2015
Posts: 56

### Finding the greatest common factor (GCF)

Hi everyone
I would like to greater a batch file that allows the user to enter 2 or three numbers and the file echo's the GCF of the numbers so if the user enters

``````3
6``````

The code displays

``3``

If the user inputs

``````25
50
100``````

The code will echo

``25``

Thanks ~Batcher

Offline

## #2 05 Nov 2016 14:38

Aacini
Member
Registered: 05 Dec 2012
Posts: 115

### Re: Finding the greatest common factor (GCF)

Are you asking us for the method used to get the GCF of two or three numbers? You may review it from this Wikipedia page.

Online

## #3 05 Nov 2016 14:52

Batcher
Member
Registered: 20 Jul 2015
Posts: 56

### Re: Finding the greatest common factor (GCF)

Aacini wrote:

Are you asking us for the method used to get the GCF of two or three numbers? You may review it from this Wikipedia page.

I was looking for a batch file that could do this Im sure there is a more efficient way than what I'm trying

``````Set /a num=input/2
Set /a numa=num*2
if %num% EQU %input% set divisora="2, "
Set /a num=input/3
Set /a numa=num*3
if %num% EQU %input% set divisorb="3, "
Set /a num=input/4
Set /a numa=num*4
if %num% EQU %input% set divisorc="4, "
:: and so on
Echo %divisora%%divisorb%%divisorc%................................``````

Last edited by Batcher (05 Nov 2016 14:52)

Offline

## #4 05 Nov 2016 18:16

Aacini
Member
Registered: 05 Dec 2012
Posts: 115

### Re: Finding the greatest common factor (GCF)

Ok. I read the Wikipedia article and chose the Binary method, so I copied this section:

``````Input: a, b positive integers
Output: g and d such that g is odd and gcd(a, b) = g×2d

d := 0
while a and b are both even do
a := a/2
b := b/2
d := d + 1
while a ≠ b do
if a is even then a := a/2
else if b is even then b := b/2
else if a > b then a := (a – b)/2
else b := (b – a)/2
g := a
output g, d``````

... into a Batch file and just inserted the modifications required in order to convert the operations into valid (and efficient) Batch code. This is the result:

``````@echo off
setlocal

:loop
set "num1="
set /P "num1=Enter first number:  "
if not defined num1 goto endLoop
set "num2="
set /P "num2=Enter second number: "
if not defined num2 goto endLoop
call :gcd %num1% %num2%
goto loop
:endLoop
goto :EOF

:gcd
rem Input: a, b positive integers

set /A "a = %1, b = %2, d = 0, aANDbEVEN = (a&1) + (b&1)"
:while1 a and b are both even do
if %aANDbEVEN% neq 0 goto endwhile1
set /A "a >>= 1, b >>= 1, d += 1, aANDbEVEN = (a&1) + (b&1)"
goto while1
:endwhile1
:while2 a NEQ b do
if %a% equ %b% goto endwhile2
set /A "aIsEven = a&1, bIsEven = b&1"
if %aIsEven% equ 0 ( set /A "a >>= 1"
) else if %bIsEven% equ 0 ( set /A "b >>= 1"
) else if %a% GTR %b% ( set /A "a = (a - b)/2"
) else set /A "b = (b - a)/2"
goto while2
:endwhile2

rem Output: g and d such that g is odd and gcd(a, b) = g×2^d
rem g := a
rem output g, d
set /A "gcd = a * (1<<d)"
echo The GCD is %gcd%
echo/
exit /B``````

Antonio

Online

## #5 06 Nov 2016 12:27

Batcher
Member
Registered: 20 Jul 2015
Posts: 56

Thank you!

Offline

## #6 06 Nov 2016 14:34

Batcher
Member
Registered: 20 Jul 2015
Posts: 56

### Re: Finding the greatest common factor (GCF)

Could I find the GCF between three numbers I tried modifying the code but I'm not sure if I did it correctly. The bottom portion is also a bit complicated so I wasn't sure how to change anything there.

``````@echo off
setlocal

:loop
set "num1="
set /P "num1=Enter first number:  "
if not defined num1 goto endLoop
set "num2="
set /P "num2=Enter second number: "
if not defined num2 goto endLoop
set "num3="
set /P "num3=Enter third number: "
if not defined num3 goto endLoop
call :gcd %num1% %num2% %num3%
goto loop
:endLoop
goto :EOF

:gcd
rem Input: a, b, c positive integers

set /A "a = %1, b = %2, c = %3, d = 0, aANDbANDcEVEN = (a&1) + (b&1) + (c&1)"
:while1 a and b are both even do
if %aANDbANDcEVEN% neq 0 goto endwhile1
set /A "a >>= 1, b >>= 1, c >>=1, d += 1, aANDbANDcEVEN = (a&1) + (b&1) + (c&1)"
goto while1
:endwhile1
:while2 a NEQ b do
if %a% equ %b% goto endwhile2
set /A "aIsEven = a&1, bIsEven = b&1"
if %aIsEven% equ 0 ( set /A "a >>= 1"
) else if %bIsEven% equ 0 ( set /A "b >>= 1"
) else if %a% GTR %b% ( set /A "a = (a - b)/2"
) else set /A "b = (b - a)/2"
goto while2
:endwhile2

rem Output: g and d such that g is odd and gcd(a, b) = g×2^d
rem g := a
rem output g, d
set /A "gcd = a * (1<<d)"
echo The GCD is %gcd%
echo/
exit /B``````

Offline

## #7 08 Nov 2016 21:14

Batcher
Member
Registered: 20 Jul 2015
Posts: 56

...

Offline

## #8 10 Nov 2016 16:20

Aacini
Member
Registered: 05 Dec 2012
Posts: 115

### Re: Finding the greatest common factor (GCF)

``````@echo off
setlocal EnableDelayedExpansion

:loop
set "num1="
set /P "num1=Enter first number:  "
if not defined num1 goto endLoop
set "num2="
set /P "num2=Enter second number: "
if not defined num2 goto endLoop
set "num3="
set /P "num3=Enter third number:  "
if not defined num3 goto endLoop
call :gcd3 %num1% %num2% %num3%
goto loop
:endLoop
goto :EOF

:gcd3
rem Input: a, b, c positive integers

set /A "a = %1, b = %2, c = %3, d = 0, aANDbANDcEVEN = (a&1) + (b&1) + (c&1)"
:while1 a and b and c are all even do
if %aANDbANDcEVEN% neq 0 goto endwhile1
set /A "a >>= 1, b >>= 1, c >>=1, d += 1, aANDbANDcEVEN = (a&1) + (b&1) + (c&1)"
goto while1
:endwhile1
:while2 a NEQ b NEQ c do
if %a% equ %b% if %b% equ %c% goto endwhile2
set /A "aIsEven = a&1, bIsEven = b&1, cIsEven = c&1"
if %aIsEven% equ 0 ( set /A "a >>= 1"
) else if %bIsEven% equ 0 ( set /A "b >>= 1"
) else if %cIsEven% equ 0 ( set /A "c >>= 1"
) else (
if !a! lss !b! set /A t=a, a=b, b=t
if !b! lss !c! set /A t=b, b=c, c=t
if !a! lss !b! set /A t=a, a=b, b=t
set /A "a = (a - c)/2"
)
goto while2
:endwhile2

rem Output: g and d such that g is odd and gcd(a, b, c) = g×2^d
rem g := a
rem output g, d
set /A "gcd = a * (1<<d)"
echo The GCD is %gcd%
echo/
exit /B``````

Antonio

Online