(Python/파이썬) - 백준(BOJ) 1630번 : 오민식

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

1630번: 오민식

---

• 문제 : 

오민식을 만족하는 수: 1보다 크거나 같고, N보다 작거나 같은 모든 자연수로 나누어 떨어지는 수.

 

영식이와 다솜이는 N이 주어졌을 때, 오민식을 만족하는 가장 작은 수가 궁금해졌다. 그 수를 구하는 프로그램을 작성하시오.

 

 

 

---

• 풀이 :

수학 문제였습니다. 

 

 

1부터 N까지 모든 수 사이의 최소공배수를 구하기 위해 각 N까지의 각 소수가 몇 번 곱해졌는지 확인하고 이 값을 정답에 곱해주는 식으로 계산했습니다. 또한. nums 배열을 사용하여 이미 확인한 수는 중복확인하지 않도록 해주었습니다.

 

 

 

---

• 소스코드 : 

N = int(input())
nums = [False for _ in range(10**6+1)]
answer = 1
for i in range(2,N+1):
    if nums[i]: continue
    t = 1
    for j in range(i,N+1,i):
        nums[j] = True
        tmp = j
        cnt = 0
        while tmp > 1 and tmp % i == 0:
            tmp //= i
            cnt += 1
        t = max(t,cnt)
    for _ in range(t):
        answer = (answer*i) % 987654321
print(answer)