1. 최소공배수, 최대공약수, 소수
- 최대공약수를 구하는 방법
💡
유클리드 호제법
2개의 자연수 a, b(a>b)에 대해서 a % b = r 일 때, a와 b의 최대공약수는 b와 r의 최대공약수와 같다.
이 과정을 반복해서 나머지가 0이 되었을 때, 이 때 나누는 수가 a 와 b의 최대 공약수 이다.
# 공통인 약수 중 가장 큰 수 (GCD)
# gcd : greatest common divisor
# a > b
def gcd(a,b) :
r = 0 # 나머지
# a를 나누어 떨어질 때까지 나눈다.
while b != 0:
r = a % b
a = b
b = r
return a
2. 최소공배수를 구하는 방법
# 두 수에 서로 공통으로 존재하는 배수 중 제일 작은 수
# 최소 공배수의 성질
# 두 수 a,b의 최소공배수는 axb를 a,b의 최대공약수로 나눈 것과 같다.
def lcm(a,b):
return a*b//gcd(a,b)
- 소수 인지 아닌지 판별하는 방법
# 약수가 1과 자기 자신만 있는 수 (Prime number)
def is_prime(n):
if (n<2):
return False
for i in range(2,n):
if n%i == 0:
return False
return True
💡
에라토스테네스의 체
수학자 에라토스테네스가 고안한 방법. 마치 체로 걸러내듯이 작동.
def get_prime(n):
arr = [True] * (n+1) # 일단 n까지의 숫자를 다 소수라고 표시
for i in range(2, n):
if arr[i]: # 만약 i 번째 수가 소수라면,
# 소수의 배수를 모두 소수가 아니라고 체크한다.
for j in range(i+i, n+1, i):
arr[j] = False
return [i for i in range (2, n+1) if arr[i] ==True]
get_prime(100)이 때, n까지 다 검사하지 않고, n의 제곱근 까지만 검사해서 최적화를 시킬 수 있다.
n = a * b라고 나타낼 수 있을 때, n'를 n의 제곱근이라 하자.
n = n' * n' 여기서 a >= n' 일 때, a*b = n' * n' = n 이므로, b < n'
따라서 n' 까지만 검사하면, 두 수 a, b 중에 작은 수 b 까지만 검사해봐도
(즉, a는 검사를 하지 않아도) 소수 인지 아닌지 판별이 가능하다.def get_prime(n):
arr = [True] * (n+1) # 일단 n까지의 숫자를 다 소수라고 표시
m = int((n)**0.5)
for i in range(2, m+1):
if arr[i]: # 만약 i 번째 수가 소수라면,
# 소수의 배수를 모두 소수가 아니라고 체크한다.
for j in range(i+i, n+1, i):
arr[j] = False
return [i for i in range (2, n+1) if arr[i] ==True]
get_prime(100)
Uploaded by N2T