[Python] BOJ 백준 21919번 소수최소공배수

문제

행복이는 길이가 N인 수열 A에서 소수들을 골라 최소공배수를 구해보려고 한다.

행복이를 도와 이를 계산해주자.

첫째 줄에 수열 A의 길이 N이 주어진다. (1≤N≤10,000)

그 다음줄에는 수열 A의 원소 Ai가 공백으로 구분되어 주어진다. (2≤Ai≤1,000,000)

답이 2**63 미만인 입력만 주어진다.

풀이

최대공약수, 최소공배수를 구하는 함수를 이용했다. 소수들의 최소공배수를 구할 때,

소수들은 서로 최대공약수가 1이기 때문에 그냥 전부 곱해주면 된다.

from math import sqrt
import sys

si = sys.stdin.readline

n = int(si())
arr = list(map(int, si().split()))
prime_list = []


def is_prime(x):
    for num in range(2, int(sqrt(x)) + 1):
        if x % num == 0:
            return
    prime_list.append(x)


def gcd(a, b):
    while b > 0:
        a, b = b, a % b
    return a


def lcm(a, b):
    return (a * b) // gcd(a, b)


for z in arr:
    is_prime(z)

answer = 1

if prime_list:
    for p in prime_list:
        answer = lcm(answer, p)
    print(answer)
else:
    print(-1)