[Python] 백준 21919 - 소수 최소 공배수 문제 풀이

Overview

BOJ 21919번 소수 최소 공배수 Python 문제 풀이
분류: Math (수학)

---

문제 페이지

https://www.acmicpc.net/problem/21919

---

풀이 코드

from sys import stdin


n = int(stdin.readline())
nums = set(list(map(int, stdin.readline().split())))

is_prime = [False, False] + [True] * (1000000 - 1)
for i in range(2, len(is_prime)):
    if not is_prime[i]:
        continue
    for j in range(2 * i, len(is_prime), i):
        is_prime[j] = False

res = 1
for num in nums:
    if is_prime[num]:
        res *= num

if res == 1:
    res *= -1
print(res)

에라토스테네스의 체를 이용하여 범위 내의 소수를 모두 구하고, 모두 곱하여 답을 구한다.