[Algorithm] BAEKJOON 21919번: 소수 최소 공배수 (Python)

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

 

 

문제

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

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

 

입력

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

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

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

 

출력

첫째 줄에 소수들의 최소공배수를 출력한다.

만약 소수가 없는 경우는 -1을 출력한다.

 

 

 

 

풀이

수열 A의 모든 원소에 대해 소수 판정을 먼저 해준 다음 파이썬의 math 라이브러리에 있는 최소 공배수 함수인 lcm 함수를 활용하여 해결하였다.

 

 

Python 소스 코드

import math

N = int(input())
A = list(map(int, input().split()))

# 소수를 저장할 리스트
prime_numbers = []

# 수열에서 소수 추출
for number in A:
    is_prime = True
    # 2부터 number의 제곱근까지 나누어 떨어지는지 확인
    for divisor in range(2, math.isqrt(number) + 1):
        if number % divisor == 0:
            is_prime = False
            break
    # 소수이면 prime_numbers 리스트에 추가
    if is_prime:
        prime_numbers.append(number)

# 소수가 없으면 -1 출력
if len(prime_numbers) == 0:
    print(-1)
else:
    # 소수들의 최소공배수 계산 및 출력
    print(math.lcm(*prime_numbers))