Math15소수 최소 공배수(21919)

문제

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

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

입력

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

그 다음줄에는 수열 A의 원소 A2가 공백으로 구분되어 주어진다. (2 <= A <= 1,000,000) 
답이 2의 63제곱 미만인 입력만 주어진다.

출력

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

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

풀이

• 구하는 것이 소수이므로, 속도를 위해 제곱근 까지만 for문 돌려 소수인지 판별
• 최소 공배수는 (기준되는 수들의 곱) / (최대 공약수) 이지만 최소공배수를 구해야하는 수들이 소수이므로 최대공약수는 모두 1이다. 따라서 prime이라는 배열을 만들어 소수를 넣고 모두 곱한 값을 출력하자 !

코드

import sys
sys.stdin = open("input.txt","rt")
import math
def input():
    return sys.stdin.readline().rstrip()

# 소수 판별
# 이 부분에서 시간초과
def primenumber(x):
    for i in range (2, int(math.sqrt(x) + 1)):	# 2부터 x의 제곱근까지의 숫자
        if x % i == 0:		# 나눠떨어지는 숫자가 있으면 소수가 아님
        	return False
    return True				# 전부 나눠떨어지지 않는다면 소수임

#1 x 8 = 8
#2 x 4 = 8
#4 x 2 = 8
#8 x 1 = 8
#앞서 말했듯, 1과 자기자신을 제외한 약수가 존재하는지 확인하려면, 자기자신의 제곱근(루트)까지만 확인하면 된다.
#어차피 약수들이 대칭적으로 짝을 이뤄서 8을 완성하기 때문이다.
#루트8은 약 2.8정도이므로 자연수 2까지만 확인해서 8에 나눠떨어지는지 확인하면 된다.

def multifly(listA):
    listA = set(listA) # 중복 제거
    res = 1
    for x in listA:
        res *= x
    return res

if __name__ == "__main__":
    N = int(input())
    arr = list(map(int,input().split()))
    prime = []

    for i in range(N):
        if primenumber(arr[i]):
            prime.append(arr[i])
    
    if len(prime) == 0:
        print(-1)
        exit()

    print(multifly(prime))    
    # A, B, C의 최소공배수
    # ① A와 B의 최소공배수를 구한다.
    # ② ①에서 구한 A와 B의 최소공배수와 C의 최소공배수를 구한다.
    # 야 근데 소수의 최소 공배수는 다 곱하면 되므로 최대 공약수를 구할 핓요가 없지 !!!

배운 것

1.이 문제에서 많이 틀렸던 이유는
중복되는 소수가 온다는걸 깜빡했었다.
즉 2 2 3 5 7 이라하면, 전체를 그냥 곱하기만 하면, 420이 된다.
set 자료구조 이용해서 중복을 피한다 !!

2. 소수를 구할때 속도를 빠르게하려면, math 라이브러리를 활용하여
   제곱근 까지만 소수를 확인한다. 어차피 약수는 대칭적으로 같기 때문!
   for i in range (2, int(math.sqrt(x) + 1)):

   # 이런식으로 2부터 x의 제곱근까지의 숫자를 구한다.

   #1 x 8 = 8
   #2 x 4 = 8
   #4 x 2 = 8
   #8 x 1 = 8
   #앞서 말했듯, 1과 자기자신을 제외한 약수가 존재하는지 확인하려면, 자기자신의 제곱근(루트)까지만 확인하면 된다.

코멘트