(백준 알고리즘 문제풀이) 21919번 소수 최소 공배수

문제

문제 링크

 

문제 접근

• 소수를 탐색하는 함수를 구현한다.
• 소수라면 prime 리스트에 deque를 이용하여 추가시킨다.
• 소수가 존재하지 않는다면 -1을 출력한다.
• 만약 소수가 존재한다면 pop을 두번해서 최소 공배수를 구하는 공식 (x * y / 최대공약수)을 이용하여 소수의 리스트가 1이 될때까지 반복한다.

코드

import sys, math
from collections import deque
input = sys.stdin.readline


def is_prime(num):
    if num == 1:
        return False
    if num % 2 == 0:
        if num == 2:
            return True
        return False
    for i in range(3, int(math.sqrt(num)) + 1):
        if num % i == 0:
            return False
    return True


n = int(input())
a = list(map(int, input().split()))
prime_num = deque()
for i in a:
    if is_prime(i):
        prime_num.appendleft(i)

if prime_num:
    for i in range(len(prime_num)-1):
        if len(prime_num) >= 2:
            x = prime_num.popleft()
            y = prime_num.popleft()
            prime_num.appendleft(x * y // math.gcd(x, y))
    print(prime_num.pop())
else:
    print(-1)