China DOS Union

I saw that lxmxn was playing with a batch script to find prime numbers, so I also played one, but this one is much easier. There is no fault tolerance check for input, and it is not guaranteed that the result will not have an overflow error. It is just a boring thing for leisure:

@echo off

setlocal enabledelayedexpansion



:begin

cls

set flag=

set num1=

set num2=

set /p num1= Please enter the first number:

set /p num2= Please enter the second number:

if %num1% leq %num2% (set min=%num1%) else set min=%num2%

:: This if statement can be changed to if %num1% gtr %num2% set /a num1=%num2%,num2=%num1%, 

:: to reduce the number of variables, then the next %min% in the for statement has to be modified accordingly to %num1% 

for /l %%i in (%min%,-1,2) do (

    set GCD=%%i

    set /a mod1=%num1%%%%%i

    set /a mod2=%num2%%%%%i

    if !mod1! equ 0 if !mod2! equ 0 set flag=1&goto end

)



:end

if defined flag (

    set /a LCM=%num1%/%GCD%*%num2%

    echo The greatest common divisor of %num1% and %num2% is %GCD%, and the least common multiple is !LCM!

) else (

    set /a LCM=%num1%*%num2%

    echo The greatest common divisor of %num1% and %num2% is 1, and the least common multiple is !LCM!

)

pause

goto begin

[ Last edited by namejm on 2007-1-24 at 02:59 PM ]

Hehe. Just support it.

Brother's code is really wonderful. I have a small question. The greatest common divisor of two numbers can be 1. Why display that there is no greatest common divisor? In mathematics, if two numbers are coprime, then their greatest common divisor is 1.

Attached is a piece of code that does not use the for statement

@echo off

set/p a=Enter the first number

set/p b=Enter the second number

set/a ab=%a%*%b%

cls&echo.&echo/&echo\

echo %a% and %b%'s Greatest Common Divisor  Least Common Multiple

if %a% lss %b% goto restart



:loop

set/a num_=%a%%%%b%

if %num_% gtr 0 set/a a=%b%&set/a b=%num_%&goto loop

goto show



:restart

set a=%b%&set b=%a%

goto :loop



:show

set/a num=%ab%/%b%

echo                     %b%                %num%

pause>nul

[ Last edited by ccwan on 2007-1-25 at 06:38 AM ]

Re ccwan 『Post #3』:

　　sorry, basic concepts were not remembered well, and a junior mistake was made.

　　Your code uses the method of successive division to calculate the greatest common divisor, which is indeed a good idea, and the speed is much faster than mine. For example, when testing with 52317 and 75569, your code instantly finds the greatest common divisor (although there was an error when calculating the least common multiple), while mine takes about 10 seconds to calculate.

　　However, my code can handle a larger range of numbers when calculating the least common multiple than yours (your code can be modified a bit). Because yours is to first multiply the two numbers and then divide by the greatest common divisor, while mine is to first divide the two numbers by the greatest common divisor and then multiply by the greatest common divisor - actually, I was a bit mechanical when calculating the least common multiple, and the code can be streamlined, that is, first divide by the greatest common divisor and then multiply by the other number.

　　In addition, your set/a num2=%a%%%b% statement actually takes advantage of the loophole in set /a operation. I don't know if you did it on purpose or didn't notice: in set /a operation, the variables involved in the operation can be directly referenced by using the variable name without using percent pairs. According to the general understanding, the meaning of this statement is that %a% and %b% do % operation, but there is no % operator in batch processing's set/a (although there is a % operator in CMD, the preprocessing mechanism in batch processing will not recognize a single % as a modulus operator). In fact, the operation is performed according to %% operation. The possible process is: the CMD preprocessing mechanism thinks that the priority of %% is higher than the reference of percent pairs, so it expands the modulus operator first and then processes the reference of variables. At this time, it is %a modulo b%. In the set /a operation, the variable a modulo b is not found, so the percent signs before and after are discarded, and it becomes using the value of a modulo the value of b. This process is only a speculation and may not be correct. It is suggested that you change this statement to set/a num2=a%%b or set/a num2=%a%%%%b% to avoid misunderstanding.

[ Last edited by namejm on 2007-1-24 at 04:00 PM ]

Thanks to brother jm's guidance, my consideration is: In the statement `set/a num2=%a%%%b%`, if it is changed to `a%%b` according to brother's meaning, in cmd operation, it will be regarded as `a%b`, and then the values of a and b will be searched to calculate; while my code in cmd will directly take the value of a, and then take modulo b. If a = 8, the operation formula is `set/a num2=8%b`, which reduces the search for one value and will not have an error.

This can be seen through experiments under cmd.

For brother's objection, this is exactly the result of my lack of knowledge, and I can't fundamentally understand its operation mechanism. I still change it here to `set/a num2=%a%%%%b%`, which is easier to understand.

[ Last edited by ccwan on 2007-1-25 at 03:50 AM ]

Original post

The Euclidean algorithm is a kind of general algorithm...

Hehe, it turns out someone has already done it. I didn't search the old posts carefully enough, resulting in duplicate content. Guilty.

But that post appeared as a post for checking errors, and what's provided here is another kind of idea. It seems inappropriate to merge the topics for now. Let's see if there are other relatively unconventional algorithms or in-depth analyses emerging.

Brother namejm and Brother ccwan wrote very good code. The Euclidean algorithm is indeed the best algorithm for finding the greatest common divisor and common multiple, and it is also the most commonly used method in daily life.

When finding the common divisor, it assigns the dividend and the remainder to the divisor and dividend for the next operation respectively until the remainder is 0.

@echo off

set /p x=Please enter the first number:

set /p y=Please enter the second number:

set /a m=x,n=y

if %x% lss %y% set /a x=%y%,y=%x%

:go

set /a r=x%%y,x=y,y=r

if %y% neq 0 goto go

set /a p=m*n,z=p/x

echo The greatest common divisor of %m% and %n% is:%x%

echo The least common multiple of %m% and %n% is:%z%

pause

[ Last edited by pengfei on 2007-1-25 at 10:32 AM ]

Temporarily unable to fully understand, first COPY it down and look at it slowly.

....

@echo off&setlocal enabledelayedexpansion

set /p num1= Please enter the first number:

set /p num2= Please enter the second number:

if %num1% geq %num2% (set g=%num1%&set l=%num2%) else set g=%num2%&set l=%num1%

:loop

set/a b+=g,mod=b%%l

if not %mod%==0 goto loop

set/a a=g*l/b

echo The greatest common divisor of %num1% and %num2% is %a%, and the least common multiple is %b%

pause