#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: 116

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: 116

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

Re: Finding the greatest common factor (GCF)

Thank you!  smile

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

Re: Finding the greatest common factor (GCF)

...

Offline

#8 10 Nov 2016 16:20

Aacini
Member
Registered: 05 Dec 2012
Posts: 116

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

Board footer

Powered by FluxBB