📚사전지식

유클리드 호제법

image

x,y의 최대공약수를 구할 때, 나머지를 계속 구해서 다시 대입하다가 나머지가 0이 될 때의 나누는 값이 GCD(최대공약수)

그리고 x와 y를 곱하고 그 둘의 최대공약수로 나눌 때 몫은 최소공배수(LCM)가 된다.

최소공배수, 최대공약수를 구하는 문제에 적용할 수 있다.

파이썬 식

def GCD(x,y):	
	while y: #y가 자연수일 때
	x, y = y , x %y
return x

def LCM(x,y):
	return (x * y) // GCD(x,y)

Math 라이브러리 사용하기

최대공약수

import math

math.gcd(10,20,30)

최소공배수

import math

math.lcm(10,20,300)

소수판정

브루트포스

그냥 숫자 N이 주어졌을 경우 N까지 일일이 나눗셈을 실행하는 방법

def is_prime_number(n):
	for i in range(2,n):
    	if i % n == 0:
        	return False
	return True

시간복잡도: O(X)

개선 알고리즘

숫자 N이 주어졌을 경우 N의 제곱근까지만 나눗셈을 실행하는 방법

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

시간복잡도: O(N/2)

에라토스테네스의 채

숫자 N이 주어졌을 경우 N의 제곱근까지 나눗셈을 실행하지만, 이 경우에는 리스트를 만들어서 나눗셈을 실행하는 수에서 자기 자신을 제외한 배수들을 제거하면서 나눗셈을 실행하는 방법으로 시간복잡도는 O(NlogN)지만, 문제는 N까지의 숫자를 담을 공간이 필요하기 때문에 메모리를 많이 잡아먹는다.(O(N)만큼! )

n = int(input())
lst = [True for i in range(2,n+1)]
def is_prime_number(n): #lst에 소수만 남도록 하게 함
	for i in range(2,math.sqrt(n)):
    	if lst[i] == True:
        	j = 2
            while x * j < n:
            	lst[x*j] = False
                j += 1

시간복잡도:O(NlogN)

공간복잡도:O(N)