[백준] 21919. 소수 최소 공배수
문제
풀이
- 에라토스테네스의 체를 사용하여 주어진 수의 최댓값 까지 소수를 전부 구해놓음.
- 주어진 배열에서 for문을 돌며 소수인 것들 만 res배열에 넣어줌.
- res배열이 비어있을 경우 소수가 없단 뜻이므로 -1 print함.
- 아닐 경우 res배열에 for문을 돌며 최소공배수를 구해줌.
(서로를 곱하고, 서로의 최대공약수로 나눠주면 최소공배수가 됨.)
코드
import sys
import math
def primeList(n : int) :
prime = [True] * (n+1)
prime[1] = False
m = int(math.sqrt(n))
for i in range(2, m+1) :
if prime[i] == True :
for j in range(i+i, n+1, i) :
prime[j] = False
return [i for i in range(2, n+1) if prime[i]]
def solution() :
n = int(sys.stdin.readline())
nums = list(map(int, sys.stdin.readline().split()))
tmp = primeList(max(nums))
res = []
for n in nums :
if n in tmp :
res.append(n)
if not res :
print(-1)
else :
calc = res[0]
for r in res :
calc = (r * calc) // math.gcd(r, calc)
print(calc)
solution()
Author And Source
이 문제에 관하여([백준] 21919. 소수 최소 공배수), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@tldjfj123/백준-21919.-소수-최소-공배수
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
- 에라토스테네스의 체를 사용하여 주어진 수의 최댓값 까지 소수를 전부 구해놓음.
- 주어진 배열에서 for문을 돌며 소수인 것들 만 res배열에 넣어줌.
- res배열이 비어있을 경우 소수가 없단 뜻이므로 -1 print함.
- 아닐 경우 res배열에 for문을 돌며 최소공배수를 구해줌.
(서로를 곱하고, 서로의 최대공약수로 나눠주면 최소공배수가 됨.)
코드
import sys
import math
def primeList(n : int) :
prime = [True] * (n+1)
prime[1] = False
m = int(math.sqrt(n))
for i in range(2, m+1) :
if prime[i] == True :
for j in range(i+i, n+1, i) :
prime[j] = False
return [i for i in range(2, n+1) if prime[i]]
def solution() :
n = int(sys.stdin.readline())
nums = list(map(int, sys.stdin.readline().split()))
tmp = primeList(max(nums))
res = []
for n in nums :
if n in tmp :
res.append(n)
if not res :
print(-1)
else :
calc = res[0]
for r in res :
calc = (r * calc) // math.gcd(r, calc)
print(calc)
solution()
Author And Source
이 문제에 관하여([백준] 21919. 소수 최소 공배수), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@tldjfj123/백준-21919.-소수-최소-공배수
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
import sys
import math
def primeList(n : int) :
prime = [True] * (n+1)
prime[1] = False
m = int(math.sqrt(n))
for i in range(2, m+1) :
if prime[i] == True :
for j in range(i+i, n+1, i) :
prime[j] = False
return [i for i in range(2, n+1) if prime[i]]
def solution() :
n = int(sys.stdin.readline())
nums = list(map(int, sys.stdin.readline().split()))
tmp = primeList(max(nums))
res = []
for n in nums :
if n in tmp :
res.append(n)
if not res :
print(-1)
else :
calc = res[0]
for r in res :
calc = (r * calc) // math.gcd(r, calc)
print(calc)
solution()
Author And Source
이 문제에 관하여([백준] 21919. 소수 최소 공배수), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@tldjfj123/백준-21919.-소수-최소-공배수저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)