[백준 17436] 소수의 배수 [Python]

문제

N개의 소수와 자연수 M이 주어진다. M 이하의 자연수 중에서 N개의 소수 중 적어도 하나로 나누어 떨어지는 수의 개수를 세어보자.

입력

첫째 줄에 N(1 ≤ N ≤ 10)과 M(1 ≤ M ≤ 1012)이 주어진다. 둘째 줄에는 N개의 소수가 주어진다. 입력으로 주어지는 소수는 100보다 작거나 같으며, 같은 소수가 두 번 이상 주어지지 않는다.

출력

첫째 줄에 M 이하의 자연수 중에서 N개의 소수 중 적어도 하나로 나누어 떨어지는 수의 개수를 출력한다.

---

풀이

M이하의 자연수 중에서 주어진 N개의 소수 중 적어도 하나로 나누어 떨어지는 수의 개수를 구해야 한다.

즉, M이하의 자연수 중 N개의 소수들에 대한 배수로 이루어진 합집합의 원소 수를 구하는 문제다.

이는 포함 배제의 원리를 사용해 쉽게 풀이할 수 있다.

 

조합을 사용해 1 ~ N개로 이루어진 소수 집합을 구하고, 포함 배제의 원리를 적용해보자.

 i = 1일 때는 한 개의 소수만 존재하므로 lcm은 자기 자신이 된다.

i >= 2부터는 i개 소수의 lcm을 구해야 한다.

만약 lcm이 M보다 큰 경우는 무시하자.
집합의 갯수( i )가 홀수인 경우에는 M에 대한 lcm의 배수 만큼 더해주고, 짝수인 경우에는 빼면 된다.

---

소스코드

보기

---

출처

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