더이상 구글링하기 귀찮다! 그래서 정리한 수학 관련 코드
Ally의 자료를 참고해서 작성
약수
•
어떤 수 의 약수는 을 나누어 떨이지게 하는 수를 의미한다.
•
왜 범위를 제곱근으로 해야 효율적일까? 이 부분이 생각보다 이해하기는 어려운데, 제곱근까지의 범위만 구해도 모든 경우의 수가 나오기 때문이다.
from math import sqrt
def get_divisors(n):
s = set()
for i in range(1, int(sqrt(n)) + 1):
if n % i == 0:
s.add(i)
s.add(n // i)
return s
print(get_divisors(18))
Python
복사
소수
•
소수란 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수
from math import sqrt
def get_divisors(n):
s = set()
for i in range(1, int(sqrt(n)) + 1):
if n % i == 0:
s.add(i)
s.add(n // i)
return s
def is_prime(n):
return (len(get_divisors(n)) == 2)
print(is_prime(7))
print(is_prime(8))
Python
복사
최대공약수
•
어떤 두 수 , 의 최대 공약수는 , 의 공약수 중에서 가장 큰 수를 의미한다.
from math import sqrt
def get_divisors(n):
s = set()
for i in range(1, int(sqrt(n)) + 1):
if n % i == 0:
s.add(i)
s.add(n // i)
return s
def get_GCD(a, b):
set_a = get_divisors(a)
set_b = get_divisors(b)
return max(set_a & set_b)
print(get_GCD(12, 8))
Python
복사
•
유클리드 알고리즘은 최대 공약수를 빠르게 구하는 알고리즘이다.
•
a > b
def gcd(a, b):
if b == 0:
return a
gcd(b, a % b)
print(gcd(12, 8))
Python
복사
최소공배수
•
어떤 두 수 , 의 최소 공배수는 , 의 공배수 중에서 가장 작은 수를 의미한다.
from math import sqrt
def get_divisors(n):
s = set()
for i in range(1, int(sqrt(n)) + 1):
if n % i == 0:
s.add(i)
s.add(n // i)
return s
def get_GCD(a, b):
set_a = get_divisors(a)
set_b = get_divisors(b)
return max(set_a & set_b)
def get_LCM(a, b):
return (a * b // get_GCD(a, b))
print(get_LCM(12, 8))
Python
복사
소인수분해
•
소인수분해는 어떤 수 을 소수(prime number)의 곱으로만 나타내는 것을 의미한다.
•
조금 이상한 부분이 소수가 아닌 부분도 들어갈 수 있는거 아닌가?
def get_primes(n):
primes = []
for i in range(2, n + 1):
while n % i == 0:
primes.append(i)
n //= i
return primes
print(get_primes(60))
print(get_primes(37))
Python
복사
에라토스테네스의 체
from math import sqrt
N = 120
is_prime = [True] * (N + 1) # 처음에는 모두 true로 초기화
is_prime[1] = False # 1은 소수가 아니므로
# 에라토스테네스의 체 알고리즘
for i in range(2, int(sqrt(N)) + 1):
if not is_prime[i]:
continue
for j in range(2 * i, N + 1, i):
is_prime[j] = False
for i in range(1, N + 1):
print(i, is_prime[i])
Python
복사