https://www.acmicpc.net/problem/2609
시간 1초, 메모리 128MB
input :
- A B(1 <= A, B <= 10,000)
output :
- 최대공약수, 최소 공배수 출력.
A의 약수들을 저장할. 1차원 리스트. B의 약수들 저장할. 1차원 리스트.
반복문의 경우. index라는 변수를 두고. index의 값이 계속 작아지는 형식.(약수들 1 이면 index 가 12, 약수가 2이면 index 가 6)
이렇게 가다가 어느 순간 나누기가 안 되고 index를 초과 하면 더 이상 약수가 없는것.
약수들은 다 구하면 정렬 해주자.
... 유클리드 호제법?
a와 b 의 최대공약수는 (a를 b로 나눈 나머지)와 b 의 최대공약수와 같다.
큰 수를 작은 수로 나누어 구한 나머지로 큰 수를 대체한다. 큰 수를 작은 수로 계속 나누어서, 나누어 떨어질 때까지 반복한다. 나누어 떨어질 때(나머지가 0일 때), 나누는 수가 최대공약수이다
a, b = 315, 495
if(b>a) :
a,b = b,a
while(b!=0):
a = a % b
a, b = b, a
print(a)정답 코드 :
import sys
A, B = map(int, sys.stdin.readline().split())
if B > A:
a, b = B, A
else:
a, b = A, B
while b != 0:
a = a % b
a, b = b, a
print(a)
print(A * B // a)
A 와 B가 마지막에 최소 공배수를 구해야 하기 때문에 최대 공약수를 구할 때는 다른 변수들이 필요하다.
