[ 최대공약수, 최소공배수 ]
- 최대공약수 : a, b 중 더 작은 수까지만 체크해도 됨. 거꾸로 체크해 나가기
- 최소공배수
유클리드 호제법
- GCD(a, b) = GCD(b, a%b)
# 최대공약수(gcd) sol1
def gcd(a, b):
ret = 0
for i in range(min(a, b)): # 1부터 체크
if a % i == 0 and b % i == 0:
ret = i
return ret
# 최대공약수(gcd) sol2 => fast(가장 큰 수부터 체크해서 조건 만족시 ret)
def gcd(a, b):
for i in range(min(a, b), 0, -1): # min(a, b)부터 거꾸로 체크
if a % i == 0 and b % i == 0:
return i
# 최대공약수(gcd) sol3 (유클리드 호제법)
def gcd(a, b):
return b if a % b == 0 else gcd(b, a % b)
# a가 b의 배수일 때에는 작은 수인 b를 return, 아니면 재귀로 반복
[ 소인수분해 ]
소수 판별법 (isPrime)
- 소수 : 자기 자신 & 1 만을 약수로 갖는 수
# sol1) 2부터 N-1까지 체크. O(N)
def isPrime(N):
for i in range(2, N):
if N % i == 0 : return False # 하나라도 약수 있으면 소수 x
return True
# sol2) 2부터 sqrt(N)까지 체크. O(sqrt(N)) => fast
def isPrime(N):
i = 2
while i * i <= N: # 중간 지점까지만 약수 있는지 체크(제곱해서 체크)
if N % i == 0: return False
i += 1
return True
에라토스테네스의 체
- 소수를 구하는 방법
- 2부터 시작해서 소수 2를 뺀 2의 배수들을 모두 지우고, 그 다음 3의 배수, 5의 배수 .... 지우기 반복
def era(N):
ck, p = [False for _ in range(N+1)], [] # ck : check, p : prime(소수)
for i in range(2, N+1):
if ck[i] == True : continue # 만약 True로 지워졌으면(즉, 소수x)
p.append(i) # 아직 지워지지 않은 수들(소수)은 소수들 배열인 p에 추가
for j in range(i*i, N+1, i): # 3인 경우엔 그다음 배수인 6은 이미 2의 배수로
# 지워졌으므로, 3*3=9 부터 지우면 됨
ck[j] = True
return ck, p