약수 구하기
python
for i in range(2, x+1):
if x % i == 0:
ans.append(i)
- 생각보다 간단하다.
- 2부터 자기 자신까지 for문으로 돌리며 나머지가 0인지 확인해보는 것이다.
두 수의 최대공약수 구하기
python
def find_gcd(a, b):
while b > 0:
a, b = b, a % b
return a
- 유클리드 호제법을 이용한다.
- 계속해서 a ← b 대입하고, b ← r 대입하다보면 언젠가는 r이 0이 되는 원리.
- 이때 y값이 x, y의 최대공약수
a = 10,\; b = 15,\; a \bmod b = r \\ [10pt]
10 \bmod 15 = 10 \\ [10pt]
15 \bmod 10 = 5 \\ [10pt]
10 \bmod 5 = 0
n개의 수 최대공약수 구하기
python
# 먼저 n개의 수를 입력받는다.
arr = list(map(int, input().split())
# 두 개 알고리즘 설정 :
def find_gcd(a, b):
while b > 0:
a, b = b, a % b
return a
# n개 최대공약수 :
def gcd_n(arr):
gcd = arr[0]
for item in arr:
gcd = find_gcd(gcd, item)
return gcd
x = gcd_n(arr)
n개의 수 공약수 구하기
- n개의 수의 최대공약수를 구한다.
- 그 최대공약수의 약수들을 모으면 된다.
python
# 먼저 n개의 수를 입력받는다.
arr = list(map(int, input().split())
# 두 개 알고리즘 설정 :
def find_gcd(a, b):
while b > 0:
a, b = b, a % b
return a
# n개 최대공약수 :
def gcd_n(arr):
gcd = arr[0]
for item in arr:
gcd = find_gcd(gcd, item)
return gcd
x = gcd_n(arr)
for i in range(2, x+1):
if x % i == 0:
ans.append(i)
print(ans)