๋ฌธ์ ๋ฅผ ํ๋ค๋ณด๋ฉด ์์ฃผ ์ถ์ ๋๋ ๊ฐ๋
์ด ์๋ค.
์ฝ์, ๋ฐฐ์, ์์ + ์ต๋๊ณต์ฝ์, ์ต์๊ณต๋ฐฐ์, ์์ธ์๋ถํด...
'์๋ค'๊ณ ํด์ ๋๋๋๊ฒ ์๋๋ผ ์ดํด → ํ์ด → ์ต์ ํ ๊น์ง ๊ฐ์ผํ๋ฏ๋ก ํท๊ฐ๋ฆด๋๊ฐ ๋ง๋ค.
์ด์ฐธ์ ์ ๋ฆฌํด๋๋ ค๊ณ ํ๋ค.
๋ฌธ์
https://www.acmicpc.net/step/10
์ต๋๊ณต์ฝ์ (GCD, Greatest Common Divisor)
์ฝ์: ์ด๋ค ์๋ฅผ ๋๋์์๋ ๋๋์ด ๋จ์ด์ง๋ ์.
์ต๋๊ณต์ฝ์๋ ๋ ์์ ๊ณตํต๋ ์ฝ์ ์ค ๊ฐ์ฅ ํฐ ์๋ฅผ ๋งํ๋ค.
math.gcd()
Python์๋ math๋ชจ๋์ด ์๋๋ฐ, ์ด ๋ชจ๋์ gcd()ํจ์๋ฅผ ์ฌ์ฉํ๋ฉด ์ต๋๊ณต์ฝ์๋ฅผ ์ฝ๊ฒ ๊ตฌํ ์ ์๋ค.
import math
def gcd(a, b):
return math.gcd(a, b)
print(gcd(24, 36)) # 12
ํ์ง๋ง ์์ฃผ ์ฌ์ฉํ๋ ๋ฐฉ๋ฒ์ ์๋๋ค.
์ ํด๋ฆฌ๋ ํธ์ ๋ฒ
์ฃผ๋ก ์ฐ๋ ๋ฐฉ์์ด๋ค.
๋ ์ a, b๊ฐ ์์๋ a๋ฅผ b๋ก ๋๋ ๋๋จธ์ง๋ฅผ r์ด๋ผ ํ๋ค๋ฉด, a์ b์ ์ต๋๊ณต์ฝ์๋ b์ r์ ์ต๋๊ณต์ฝ์์ ๊ฐ๋ค๋ ์๋ฆฌ๋ค.a % b == r์ผ๋, gcd(a, b) == gcd(b, r)๋ผ๋ ์๋ฆฌ๋ค.
def gcd(a, b):
while b != 0:
a, b = b, a % b
return a
print(gcd(24, 36)) # 12
a, b๋ฅผ ์
๋ ฅ๋ฐ์ ํ a๋ฅผ b๋ก, b๋ฅผ a%b(r)๋ก ๊ณ์ ์ฌํ ๋นํ๋ค.
์ฌ๊ท์ ์ผ๋ก ๋ฐ๋ณตํ๋ค b๊ฐ 0์ด ๋๋์๊ฐ a๋ฅผ ๋ฐํํ๋ค.
๋ ํฐ ์๋ฅผ a๋ก ์ง์ ํด์ฃผ๊ณ ์คํํด๋ ๋์ง๋ง ๋ฑํ ๊ทธ๋ด ํ์๋ ์๋ค.
# a % b = r
24 % 36 = 24
36 % 24 = 12
24 % 12 = 0 # ์ฌ๊ธฐ์ a, b = 12, 0์ด ๋๋ฏ๋ก ๋ฐ๋ณต๋ฌธ ์ข
๋ฃ.
์ต์๊ณต๋ฐฐ์ (LCM, Least Common Multiple)
๋ฐฐ์: ์ด๋ค ์์ ์ ์๋ฅผ ๊ณฑํ์ฌ ์ป์ ์ ์๋ ์.
์ต๋๊ณต๋ฐฐ์๋ ๋ ์์ ๊ณตํต๋ ๋ฐฐ์ ์ค ๊ฐ์ฅ ์์ ์.
์ต๋๊ณต๋ฐฐ์๋ฅผ ๊ตฌํ๋ ๋ฐฉ์์ ๊ฐ๋จํ๋ฐ, ๋ ์์ ๊ณฑ์ ์ต๋๊ณต์ฝ์๋ก ๋๋์ด ๊ตฌํ๋ฉด ๋๋ค.
์ต๋๊ณต์ฝ์ ์ฌ์ฉํ๊ธฐ
import math
def lcm(a, b):
return abs(a * b) // math.gcd(a, b)
print(lcm(24, 36)) # 72
์์ (Prime Number)
: 1๊ณผ ์๊ธฐ ์์ ์ด์ธ์ ์ฝ์๋ฅผ ๊ฐ์ง ์๋ ์.
์ฌ๊ธฐ์ ์๋ผํ ์คํ ๋ค์ค์ ์ฒด ๊ฐ๋ ์ด ์ฐ์ธ๋ค.
์๋ผํ ์คํ ๋ค์ค์ ์ฒด
2๋ถํฐ ์์ํ์ฌ ๋ฐฐ์๋ค์ ์ ๊ฑฐํด๋๊ฐ๋ ๋ฐฉ์์ด๋ค.

def sieve_of_eratosthenes(n):
primes = [True] * (n + 1)
primes[0] = primes[1] = False
for i in range(2, int(n ** 0.5) + 1):
if primes[i]:
for j in range(i * i, n + 1, i):
primes[j] = False
return [i for i in range(2, n + 1) if primes[i]]
print(sieve_of_eratosthenes(30)) # [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
์ธ๋ฑ์ค์ ๋ฒ์๋ฅผ 0๋ถํฐ n๊น์ง๋ก ์ก์๋์ผํ๊ธฐ ๋๋ฌธ์, [True]์ ๊ฐฏ์๋ฅผ (n+1)๋งํผ์ผ๋ก ์ค์ ํ๋ค.
๊ทธ ๋ค์ 2๋ถํฐ n์ ์ ๊ณฑ๊ทผ๊น์ง ์ํํ๋ค.
๋ง์ฝ primes[i]๊ฐ True๋ผ๋ฉด i์ ํด๋นํ๋ ์์ ๋ฐฐ์๋ค์ ๋ชจ๋ False๋ก ์ค์ ํ๋ค.
์ฒด๋ก ๊ฑธ๋ฌ์ฃผ๋๊ฑฐ๋ค.
์ฌ๊ธฐ์ n์ ์ ๊ณฑ๊ทผ๊น์ง๋ง ์ํํ๋ ์ด์ ๋ ๋ค์๊ณผ ๊ฐ๋ค.
์ด๋ค ํฉ์ฑ์ x๊ฐ ์๋ค๊ณ ๊ฐ์ ํด๋ณด์.
์ด ์๋ ๋๊ฐ์ ์์ a, b์ ๊ณฑ์ผ๋ก ํํํ ์ ์๋ค.
์ฆ x = a * b์ธ ์
์ด๋ค. (๋ชจ๋ ํฉ์ฑ์๊ฐ ๊ผญ ๋๊ฐ์ ์์ ๊ณฑ์ผ๋ก ํํํ ์ ์๋๊ฑด ์๋์ง๋ง ๊ทธ๋ ๋ค ์น์.)
์ฌ๊ธฐ์ a๋ b ๋ ์ค ํ๋๋ ์ ๊ณฑ๊ทผ๋ณด๋ค ์์์ผํ๋ค.
๋ง์ฝ ๋ ๋ค ์ ๊ณฑ๊ทผ๋ณด๋ค ํด ๊ฒฝ์ฐ, a * b > x๊ฐ ๋๋์
์ด๊ธฐ ๋๋ฌธ์ด๋ค.
๋ฐ๋ผ์ a, b ์ค ์ ๊ณฑ๊ทผ๋ณด๋ค ์์ ์๋ ๋ฌด์กฐ๊ฑด ์กด์ฌํ๊ณ , ๊ทธ ์์ ๋ฐฐ์ ๋ํ ์ ๊ฑฐํ ์ ์๋ค.
์๋ผํ ์คํ ๋ค์ค์ ์ฒด์์ "ํฉ์ฑ์ = ๋ ์์์ ๊ณฑ"์ผ๋ก ๊ฐ์ ํ๋ ์ด์ ๋ ๋ค์๊ณผ ๊ฐ๋ค.
- ๋ชจ๋ ํฉ์ฑ์๋ ์์์ ๊ณฑ์ผ๋ก ํํ๋ ์ ์๋ค. (์์์ ์ ์์ ๋ฐ๋ผ)
- ์ด๋ค ํฉ์ฑ์๊ฐ ๋ ๊ฐ์ ์์์ ๊ณฑ์ผ๋ก ํํ๋์ง ์๋๋ค๋ฉด, ๊ทธ ํฉ์ฑ์๋ ๋ฐ๋์ ์ ์ด๋ ํ๋์ ์ ๊ณฑ์(square number)๋ฅผ ์ธ์๋ก ๊ฐ์ง๋ค.
์์ธ์๋ถํด
: ์์ฐ์๋ฅผ ์์์ ๊ณฑ์ผ๋ก ๋ํ๋ด๋ ๊ฒ.
์๋ฅผ๋ค์ด 12 ๋ฅผ ์์ธ์๋ถํดํ๋ฉด 2 x 2 x 3 ์ด ๋๋ค.
ํน์ง
- ๋ชจ๋ ์์ฐ์๋ ์์์ ๊ณฑ์ผ๋ก ์ ์ผํ๊ฒ ํํ๋ ์ ์๋ค. (์ฐ์ ์ ๊ธฐ๋ณธ ์ ๋ฆฌ)
- ์์ธ์๋ถํด์ ๊ฒฐ๊ณผ๋ ์ค๋ฆ์ฐจ์์ผ๋ก ์ ๋ ฌ๋ ์์์ ๊ณฑ์ด๋ค.
def prime_factorization(n):
factors = []
i = 2
while i * i <= n:
if n % i == 0:
factors.append(i)
n //= i
else:
i += 1
if n > 1:
factors.append(n)
return factors
print(prime_factorization(12)) # [2, 2, 3]
print(prime_factorization(360)) # [2, 2, 2, 3, 3, 5]
์ํ๊ฐ ๋๋ ๋ค n์ด 1๋ณด๋ค ํฌ๋ค๋ฉด n ์์ฒด๊ฐ ์์๋ผ๋ ๊ฒ์ด๋ฏ๋ก, n์ appendํ๋ค.