에라토스테네스의 체(Eratosthenes Sieve)로 소수 구하기

자연수 n이 소수인지를 판별하기 위해서는 2부터 n-1까지 for 반복문을 돌려 나누어 떨어지는 숫자가 있는지 확인하는 방법을 사용할 수 있다. 하지만 이러한 일반적인 방법을 사용할 경우 O(n)의 복잡도를 갖기 때문에 시간이 초과될 것이다.

따라서 우리는 에라토스테네스의 체라는 알고리즘을 사용할 것이다.

논리

각 수가 갖는 약수는 제곱근을 기준으로 대칭을 이루기 때문에 제곱근까지만 나누어 떨어지는 숫자가 있는지 확인하면 된다.

이는 제곱근 까지의 숫자의 배수를 모두 배제시키는 알고리즘을 구현하면 된다는 것을 의미한다!

파이썬으로 구현해보자

def prime_list(n):
   # Updating a list with numbers from 0-n (assume all are prime)
   sieve = [True] * n

   m = int(n ** 0.5)
   for i in range(2, m + 1):
       if sieve[i] == True:  # i가 소수인 경우
           for j in range(i + i, n, i):  # i이후 i의 배수들을 False 판정
               sieve[j] = False

   # 소수 목록 산출
   print(sieve)
   return [i for i in range(2, n) if sieve[i] == True]

시간복잡도가 대략 O(√n)으로 줄어든다!
일정 숫자까지의 소수를 구하는 알고리즘에서 효율이 매우 증가한다.
즐겁지 아니한가?!

에라이토레타의 체를 이용한 소인수분해

같은 논리를 적용하여 소인수분해를 할 수 있다. n을 √n 으로 나눴을 때 √n 보다 큰 수가 나올 수 없다. 따라서 n이 1이 될때까지 나눠서 소인수 분해 할 필요는 없다.

그냥 코드를 보면 안다

파이썬으로 구현구현~

N = int(sys.stdin.readline().strip())
d = 2
M = N ** (0.5)

while d <= M:
    if N % d != 0:
        d +=1
    else:
        print(d)
        N //= d
if N > 1:
    print(N)

유클리드 호제로 GCD & LCM 구하기

a, b가 있을 경우 min(a,b)를 i로 설정하고 a % i == 0 and b % i ==0가 될때까지 i -= 1을 하며 while룹을 돌려도 된다. 하지만 최악의 경우 i만큼 룹을 돌아야할 수 있기 때문에 시간이 초과될 가능성이 높다.

그래서 우리는 유클리드 알고리즘을 사용해야 한다!

논리

2 개의 자연수 a, b (a > b)에 대해서 a를 b로 나눈 나머지가 r일 때, a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 재귀냄새가 물씬 나지 않는가?!

파이썬으로 구현해보자

def gcd_u(a,b):
    bigger = max(a,b)
    smaller = min(a,b)
    if smaller == 0:
        return bigger
    return gcd_u(smaller, bigger % smaller)

마찬가지로 시간이 훨씬 절약된다!

그럼 LCM은 어떻게 구하나요?

두 수 a와 b의 최소공배수는 a와 b의 곱을 a와 b의 최대공약수로 나눈 것과 같다!