[백준] 21919 소수 최소 공배수

📖 문제

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

💻 내 코드

import math
import sys

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

n=int(sys.stdin.readline())
mlist=list(map(int, sys.stdin.readline().split()))
plist=set([])
for num in mlist:
    if isPrime(num)==True:
        plist.add(num)

if len(plist)==0:
    print(-1)
else:
    res=1
    for i in plist:
        res*=i//math.gcd(res, i)
    print(res)

💡 풀이

처음 제출했던 코드

import math
import sys

def isPrime(x):
    if x<2:
        return False
    else:
        for i in range(2, x):
            if x%i==0:
                return False
    return True
        

n=int(sys.stdin.readline())
mlist=list(map(int, sys.stdin.readline().split()))
plist=[]
for num in mlist:
    if isPrime(num)==True:
        plist.append(num)

if len(plist)==0:
    print(-1)
else:
    res=1
    for i in plist:
        res*=i//math.gcd(res, i)
    print(res)

• 시간초과가 뜸

시간초과를 방지하기 위해서는

• 소수를 구할 때 직접 for문으로 2부터 n-1까지의 수로 나눠보는 것이 아닌 에라토스테네스의 체를 이용해야 한다
• 소수인 수를 저장할 때 그냥 리스트가 아닌 set또는 dict를 써주어야 한다