정수

정수란 양의 정수(자연수), 음의 정수, 0을 포함한다.

약수와 배수

어떤 정수를 나머지 없이 나눌 수 있는 수를 약수라 하고, 어떤 정수에 다른 정수를 곱하여 만들어진 수를 정수의 배수라고 한다.
예를 들어 15 / 3의 결과는 나머지 없이 몫이 5가 되므로 3과 5는 15의 약수에 해당하며 15는 3의 배수인 동시에 5의 배수라고 할 수 있다.

최대공약수와 최소공배수

두 수의 약수 중에서 서로 공통된 것을 공약수라고 하며, 공약수 중 가장 큰 수를 최대공약수(Greatest Common Divisor, GCD)라고 한다.
두 수의 배수 중에서 서로 공통된 것을 공배수라고 하며, 공배수 중 가장 작은 수를 최소공배수(Least Common Multiple, LCM)라고 한다.

최대 공약수는 유클리드 호제법을 사용하면 간단하게 구할 수 있다.

유클리드 호제법을 파이썬으로 구현할 때, 재귀를 사용하면 쉽게 구현할 수 있다.

def gcd(a,b):
	if(b == 0):
    	return a
    else:
    	gcd(b, a%b)

만약 최소공배수를 구해야 한다면 최대공약수를 사용하여 쉽게 구할 수 있으니 활용하면 좋다.

소수(Prime number)

소수란 자기 자신과 1외에는 다른 약수가 없는 수를 말한다. 예를 들어 7은 자기 자신과 1외 다른 약수가 없으므로 소수이다.
소수인지 아닌지 판별하기 위해서는 약수가 존재하는지 확인하는 방법이 있다. 소수가 아니라면 정수의 곱으로 나타낼 수 있기 때문이다.
정수 n이 소수가 아니고 두 정수의 곱 a*b로 나타낼수 있다고 가정하면 $a≤\sqrt{n}$ 또는 $b≤\sqrt{n}$이 성립한다. 즉, 2이상 $\sqrt{n}$ 이하의 인수가 반드시 존재한다.

def isPrime(num):
    if num<2:
        return False
        
    for i in range(2, int(math.sqrt(num)+1)):
        if num%i == 0:
            return False
    return True

일정한 범위의 수에서 소수를 나열하고 싶다면 에라토스테네스의 체를 활용한다. 에라토스테네스의 체란 숫자들을 체로 치듯이 걸러 소수만 남기는 방법으로 과정은 아래와 같다.
1. 찾을 범위까지의 수를 나열한 다음, 소수가 아닌 1을 우선 지운다.
2. 1 다음 큰 수인 2를 남겨두고 2의 배수를 모두 지운다.
3. 그다음 소수인 3을 남겨두고 3의 배수를 모두 지운다.
4. 더 이상 지울것이 없을 때까지 반복한다.

def sieveOfEratosthenes(n):
    n = n+1
    sieve = [0]*(n)
    
    for idx in range(2, int(math.sqrt(n))):
        if sieve[idx]: continue
        for i in range(idx*2, n, idx):
            sieve[i]=1
    
    return [i for i in range(2, n) if sieve[i] == 0]

소인수분해

소수인 약수들의 곱셈 형태로 합성수를 나타내는 것을 소인수분해라고 한다.
예) $72=2^3*3^2$

def factorization(num):
    answer = []
    
    for i in range(2, num+1):
        while num%i == 0:
            num= num/i
            answer.append(i)
        if num==0:
            break
    return answer

유리수

분자, 분모가 모두 정수인 분수로 나타낼 수 있는 수이다.
유리수의 분류

• 정수 : 양의 정수, 0, 음의 정수
• 정수가 아닌 유리수: $+{1 \over 2}$, $-{2 \over 3}$, 0.3, $0.\dot{3}$ 등

유한소수와 무한소수(decimal)

주의) 여기서 말하는 소수는 prime number가 아닌 1.2처럼 숫자와 소숫점으로 표현할 수 있는 수를 말한다.

유리수의 분수를 소수로 표현하면 ${1 \over 2}$는 0.5로 표현할 수 있다. 하지만 ${2 \over 3}=0.666666...$처럼 나눠떨어지지 않는 수도 존재한다. 이를 유한소수와 무한소수라고 부른다.

• 유한소수: 소수점 아래에 0이 아닌 숫자가 유한개인 소수
• 무한소수: 소수점 아래에 0이 아닌 숫자가 무한히 계속되는 소수

유한소수와 무한소수 구별법

1. 분자와 분모를 약분해서 기약분수(분자와 분모에 공약수가 없는 상태)로 만든다.
2. 분모를 소인수 분해 한다.
   3-1. 분모의 소인수가 2나 5로 이루어져 있다면 유한소수이다.
   3-2. 분모의 소인수가 2나 5가 아닌 경우 무한소수이다.

from fractions import Fraction 

def isFinite(denominator):
    fact = set(factorization(denominator))
    
    for i in fact:
        if i != 2 and i!= 5:
            return False

    return True