최대공약수의 정의
정수 a와 b의 겹치는 약수들 중 가장 큰 것이 최대 공약수이다. 1을 제외한 모든 약수가 하나라도 겹치지 않는다면 최대공약수는 1이다. 예를들어 4와 6의 약수 중에서 겹치는 가장 큰 약수는 2이므로 최대공약수가 2가 되는 것이다. 겹치는 약수가 없는 5와 7의 최대공약수는 1이다.
약수 목록을 구하는 파이썬 코드
fir = list(map(int, input().split()))
lists1 = []
lists2 = []
for i in range(2, int(fir[0])):
re = (int(fir[0]) / int(i)).is_integer()
if re:
lists1.append(i)
for i in range(2, int(fir[1])):
re = (int(fir[1]) / int(i)).is_integer()
if re:
lists2.append(i)
if len(lists1) == 0:
lists1.append(int(fir[0]))
if len(lists2) == 0:
lists2.append(int(fir[1]))
print(lists1)
print(lists2)
두 숫자를 띄어쓰기로 받아 각각 다음, 다다음 줄에 약수들을 출력하는 코드이다. 입력된 수는 약수 목록에서 제외된다. list 2개를 만들어서 두 숫자에 대한 약수를 반복문 안에서 집어넣어주는 형식이다. re에 따라 리스트에 더할지 말지 결정하는데, re = (int(fir[1]) / int(i)).is_integer() 한 수를 반복문 안의 수 (1~n)까지로 다 나누었을 때 정수로 나눠지는 것만 약수이다. 예를 들어서 15를 넣었다면 2로 나눴을 때는 7.5로 정수가 안나오며 3을 넣어야 정수 5로 나눠진다. 다시 4를 넣으면 정수가 아니며 5는 3으로 나누어지기 때문에 약수이다. .is_integer()로 정수인지 체크할 수 있다.
최대공약수를 구하는 파이썬 코드
size1: int = len(lists1) + 1
size2: int = len(lists2) + 1
lists3 = []
lists1.append(fir[0])
lists2.append(fir[1])
for repeat_big in range(size1):
for repeat_small in range(size2):
if lists1[repeat_big] == lists2[repeat_small]:
lists3.append(lists1[repeat_big])
lists1.pop(lists1[repeat_big])
lists2.pop(lists2[repeat_small])
lists3.sort()
print(str(fir[0]) + "의 약수는 " + str(lists1) + " 입니다.")
print(str(fir[1]) + "의 약수는 " + str(lists2) + " 입니다.")
if len(lists3) != 1:
print("두 수의 공통 약수는 " + str(lists3) + " 입니다.")
lists3.reverse()
print("따라서 최대공약수는 " + str(lists3[0]) + " 입니다.")
elif len(lists3) == 1:
print("두 수의 공통 약수가 1뿐이므로 최대공약수는 1 입니다.")
이 코드를 추가해서 최대공약수를 구할 수 있다. 반복문 안의 반복문을 돌려 브루트포스로 같은지 검사하는 방식이다. 굉장히 비효율적이고 시간복잡도도 안나오는 멍청한 코드지만 이 방법 말고는 생각이 안난다. 일단 공통 약수를 구한 다음, 공통 약수들을 정렬해서 가장 큰 값을 구하는 것이다.
최대공약수를 생각하지 않은 간단하게 약수 구하기
a = int(input())
ls = []
for repeat in range(2, a - 1):
if a % repeat == 0:
ls.append(repeat)
elif a % repeat != 0:
pass
바로 입력받아서 나눈 값이 정수인지 확인해주면 된다.
최소공배수의 정의
정수 a와 b의 겹치는 약수들 중 가장 작은 것이 최소공배수이다. 겹치는 약수가 없으면 두 정수를 곱한 것이 최소공배수이다. 7과 9의 최소공배수는 63이고, 4와 6의 최소공배수는 2이다.