21919. 소수 최소 공배수

21919. 소수 최소 공배수 문제 바로가기

문제

입력

출력

문제 접근

주어진 수열에서 소수를 먼저 구분, 그 소수를 이용해서 lcm을 구한다.
lcm()에 list를 대입할 순 없다.
따라서 list값을 lcm에 대입하는 함수를 따로 정의해서 풀이한다.
소수는 그냥 곱해서 최소 공배수를 구할 수 있다.

첫번째 코드

import sys
input = sys.stdin.readline
from math import gcd,lcm

N = int(input())
a = input().split()
a = list(map(int,a))
list = []
for i in a:
    k = 0
    for j in range(int(i**0.5)):
        if i%(j+1) == 0:
            k += 1
    if k == 1:
        list.append(i)

def lcm_list(a):
    i == a[0]
    a.remove(i)
    b = []
    for j in a:
        print("i,j :",i,j)
        b.append(lcm(i,j))
    print(b)
    lcm_list(b)
    if len(b) == 0:
        return b[0]

if len(list) != 0:
    print(lcm_list(list))
else :
    print("-1")

두번째 코드

import sys
input = sys.stdin.readline
from math import gcd,lcm,sqrt

def isPrime(a):
    a = int(a)
    k = 0
    for i in range(1,int(sqrt(a))+1):
        if a%(i) == 0:
            k+=1
    if k == 1:
        return 1
    else:
        return 0

N = int(input())
numbers = input().split()
primenums = []
for i in numbers:
    if isPrime(i) == 1:
        if i not in primenums:
            primenums.append(i)

p = 1
for i in primenums:
    p = p*int(i)

if len(primenums) == 0:
    print('-1')
else:
    print(p)

추가 메모

• for문에 list의 값을 모두 출력하고자 할 때 중간에 list를 삭제하면 list의 length만큼 반복하기 때문에 값을 모두 출력하지 못하는 경우가 발생
  예시 코드

for i in numbers:
    if isPrime(i) == 1:
        numbers.remove(i)
print(numbers)

위와 같은 코드가 있을 때 number에는 2,3,5,6,8 다섯 개의 value가 있었으나 중간에 if문을 만족하여 하나의 값이 사라졌다면 마지막 원소인 8은 i로 고려되지 않고 for문을 통과하지도 않는다.

• 소수끼리의 최소공배수는 그냥 곱으로 구할 수 있다.

• 같은 소수가 여러 개 나오는 경우도 고려한다.