[FORTRAN 기초] 알고리즘 4편: 최대공약수와 최소공배수 구하기 fortran code

최대공약수(GCD)는 두 수의 공통된 약수 중 가장 큰 수이며, 최소공배수(LCM)는 두 수의 공통된 배수 중 가장 작은 수임. 프로그래밍에서 이를 구하는 가장 효율적인 알고리즘인 '유클리드 호제법'과 수학 공식을 포트란 77 코드로 구현해 본다.

🟪 1. 데이터 영역 및 변수 선언 (Specification)

유클리드 나눗셈 회전 시 원본 값이 유실되는 것을 막기 위한 복사본 변수와 결과를 저장할 변수들을 선언함. 포트란 77 규칙에 맞춰 변수명을 6글자 이내로 압축하여 정의해야 한다.

fortran code

12345678901234567890123456789012345678901234567890123456789012345678901234567890
C      ====== 1번째 칸에 'C'를 적으면 이 줄은 주석 공간이 됨 ======
       PROGRAM GCD_LCM_MASTER
       IMPLICIT NONE
       
*      [원본 변수] 최대공약수와 최소공배수를 구할 두 개의 원본 마스터 숫자
       INTEGER ORIGN1, ORIGN2
       
*      [연산용 복사본 변수] 유클리드 나눗셈 회전 시 값이 변하므로 임시 변수 활용
       INTEGER TMPA, TMPB, CALCRE
       
*      [결과 변수] 연산이 완료된 최종 GCD, LCM 값을 담아둘 공간
       INTEGER RESGCD, RESLCM

 

 

---

🟩 2. 유클리드 호제법 루프 및 연산 실행 (Execution)

나머지가 0이 될 때까지 IF-GOTO 문장으로 회전 루프를 구동하여 최대공약수를 선출한 뒤, 연산 법칙 공식을 대입하여 최소공배수까지 일괄 산출하는 영역임.

fortran code

12345678901234567890123456789012345678901234567890123456789012345678901234567890
*      [백업 작업] 원본 마스터 값이 파괴되지 않도록 연산용 변수로 이관함
       ORIGN1 = 72
       ORIGN2 = 30
       TMPA = ORIGN1
       TMPB = ORIGN2

*      =============================================================
*      [알고리즘 A] 유클리드 호제법을 이용한 최대공약수(GCD) 추적
*      =============================================================
*      60번 레이블을 시작점으로 지정하여 나머지가 0이 될 때까지 무한 회전함
60     CALCRE = MOD(TMPA, TMPB)
       
       IF (CALCRE .NE. 0) THEN
*          나머지가 0이 아니면, 나누었던 수(TMPB)를 새로운 피제수(TMPA)로 보냄
           TMPA = TMPB
*          방금 나온 나머지(CALCRE)를 새로운 제수(TMPB)로 보낸 뒤 루프 백 실행
           TMPB = CALCRE
           GOTO 60
       ENDIF

*      루프를 탈출하는 순간 나누었던 수(TMPB)가 곧 최종 최대공약수(RESGCD)가 됨
       RESGCD = TMPB

*      =============================================================
*      [알고리즘 B] 수학 공식을 활용한 최소공배수(RESLCM) 산출
*      =============================================================
*      공식: 최소공배수 = (두 원본 수의 곱) / 최대공약수
       RESLCM = (ORIGN1 * ORIGN2) / RESGCD

*      -------------------------------------------------------------
*      [결과 출력] WRITE문과 FORMAT 연동을 통해 연산 결과 매칭 표출
*      -------------------------------------------------------------
       WRITE(*, 940) ORIGN1, ORIGN2
       WRITE(*, 950) RESGCD
       WRITE(*, 960) RESLCM

       STOP

C      =================================================================
C      [FORMAT 정의 구역] 결과 표출 규격 선언 (1~5칸 레이블)
C      =================================================================
940    FORMAT(1X, 'ORIGINAL NUMBERS : ', I3, ' AND ', I3)
950    FORMAT(1X, 'MAX GCD RESULT   : ', I3)
960    FORMAT(1X, 'MIN LCM RESULT   : ', I6)

       END

---

💡 [실무 팁] 포트란 6글자 변수명 압축과 수식 오버플로우 방어 규칙

정보처리기능사 실기 순서도 구조 분석 및 포트란 실무 코딩 시 반드시 짚고 넘어가야 할 엔지니어링 개념임.

• 6글자 변수 레이아웃 설계법
  • 앞서 문법 정리에서 다루었듯 포트란 77은 변수명을 최대 6자 이하로만 명명해야 함.
  • 이에 따라 ORIGINAL-NUM1이나 RESULT-GCD 같은 긴 이름을 단독 사용하면 에러가 터지므로, 본 실전 코드에서는 ORIGN1 (5자), RESGCD (6자), RESLCM (6자) 형태로 압축하여 컴파일러의 글자 수 파괴 현상을 원천 방어함.
• 괄호 연산을 활용한 정밀 수식 제어
  • 최소공배수를 연산하는 구절인 RESLCM = (ORIGN1 * ORIGN2) / RESGCD 구문을 보면 분자 영역에 명시적으로 괄호()를 결합해 주었음.
  • 포트란 컴파일러에게 곱셈 연산을 먼저 처리하도록 명확한 이정표를 제공하여 정수 나눗셈 시 발생할 수 있는 소수점 아래 버림 오류를 예방하고, 대량 수식 배치 구동 시의 계산 정밀도를 올바르게 유지하는 실무 필수 코딩 규칙이다.