[Python] 21919번 소수 최소 공배수

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

21919번: 소수 최소 공배수

---

 

22/09/25

 

 

간단한 에라토스테네스의 체 알고리즘을 적용하는 문제로, 그다지 어려운 문제는 아니다.

 

만약 에라토스테네스의 체 알고리즘을 잘 모르는 상태라면, 먼저 배우기를 권장한다.

---

 

문제 접근 방식:

 

 

수열들 중에서 소수들을 먼저 골라야 되고, 주어지는 숫자의 크기가 백만 이하이므로, 백만 개의 배열을 불러와 에라토스테네스의 체 알고리즘을 진행하여 소수들을 골라낸다.

 

이후 이 소수들의 최소공배수를 구하는 것이 우리의 목적이다.

 

근데 우리는 소수들끼리는 모두 최대공약수가 1이라는 사실을 알고 있다. 

때문에 최소 공배수를 구하려면 그냥 그 소수들을 전부 곱하기만 하면 된다.

 

이를 그대로 코드로 구현하면 끝인 간단한 문제이다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 21919번 소수 최소 공배수
# 에라토스테네스의 체, 소수 판정, 수학
'''
접근 방법:
수열 A의 원소 Ai의 크기가 백만 이하로 주어지므로,
백만 이하의 배열을 불러와서 에테체를 진행한다.
'''
import sys
input = sys.stdin.readline

sieve = [1 for _ in range(1000001)]
sieve[0], sieve[1] = 0, 0
for i in range(2, 1000001):
    if sieve[i] == 0:
        continue
    else:
        for j in range(2*i, 1000001, i):
            sieve[j] = 0

N = int(input())
A = list(map(int, input().rstrip().split()))
total = 1
for num in A:
    if sieve[num]:
        total *= num
        sieve[num] = 0
if total == 1:
    print(-1)
else:
    print(total)