[python/파이썬] 백준 21919 소수 최소 공배수

문제

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

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

입력

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

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

답이 263 미만인 입력만 주어진다.

출력

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

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

예제 입력 1 복사

5
2 3 5 6 8

예제 출력 1 복사

30

수열 중에 소수는 2, 3, 5가 있다.

예제 입력 2 복사

4
4 16 64 256

예제 출력 2 복사

-1

 

[소스 코드]

 

어렵지 않은 문젠데 2가지 때문에 틀렸었다.

첫 번째는 결과를 저장하기 위한 변수인 result를 0으로 초기화한 것이다.

쉬운 문제라서 아무 생각 없이 코드를 작성하다가 result를 0으로 써서 틀렸다.

 

두번째는 중복 때문이었다.

수열의 원소들을 arr 리스트에 담아서 그중에 소수인 것을 골라내려고 하였다.

아무리 봐도 틀린 부분이 없는데 자꾸 '출력 초과'가 뜨길래 이상하다 했는데

중복되는 소수가 있는 경우가 있기 때문에 중복을 제거하지 않으면 출력 초과가 뜬다고 한다.

 

import sys
import math

input = sys.stdin.readline

n = int(input())
arr = set(map(int, input().split())) 
#수열을 set이 아닌 list로 받으면 중복된 소수가 있을 수 있기에 출력초과가 뜸

tmp = [] #소수 리스트
result = 1 #곱해줄 것이므로 1로 초기화

for i in arr:
    count = 0
    for j in range(2, int(math.sqrt(i))+1): #시간초과를 방지하기 위한 범위
        if i%j==0: #소수가 아닌 경우 카운트 증가
            count += 1
    if count == 0: #소수이면 tmp에 넣기
        tmp.append(i)

if len(tmp) == 0: #소수가 없으면 -1 출력
    print(-1)
else:
    for d in tmp: # 소수들의 최소공배수는 각 수의 곱
        result = result * d
    print(result)