[백준 9359] 서로소 (python)

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

9359번: 서로소

서로소 문제

A<= x <= B 범위에 해당하는 수 중에 N과 서로소인 x의 개수를 구하는 문제

소수의 개념인 에스토라테네스의 체와 포함 배제의 원리를 조합하여 해결 할 수 있었다.

📌 문제 접근 포인트

1. N과 서로소인 것의 개수를 구해야하는데, 서로소의 정의상 두 정수를 나눌 수 있는 양의 정수가 1밖에 없다는 뜻은 소수들의 집합으로 비교하는 것을 의미한다. N 그 자체를 이용하기보단 N을 포함하고, N보다 작은 소수들을 이용해서 찾아서 계산해야한다.
2. 에라토스테네스의 체 개념을 이용해서 빠르게 소수를 구할 수 있게 구성해주자. 단순히 소수를 구하기만 해선 N의 값이 10**9에 해당하는 숫자이므로 시간이 오래걸릴 수 있다. 그렇기에 N의 크기를 작게 만들어서 연산을 진행 할 수 있게해주자.
3. 소수의 집합을 구했으면, 이제 소수를 이용해서 고를 수 있는 조합을 combination을 이용해서 뽑아주고, 거기서 뽑은 조합을 이용해 포함 배제의 원리대로 계산을 진행해주자. A와 B에 대해 각각 계산을 해주자.
4. A,B에 대해 계산하고 둘의 차이를 계산하기 위해서 A 바로 앞까지만 계산이 될수 있게 A-1부터 시작해서 계산해주고, 둘의 차이를 구하면 요구사항을 만족하는 값을 얻을 수 있다. 

⚙ 내가 푼 정답 코드

from itertools import combinations
import sys
# N에 대한 소수 집합 구해주기 (N과 서로소 체크)
def prime(n): # 소수 구하기 
    result = [] # 소수 집합
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            result.append(i)
            while n % i == 0: # n이 매우 크니 나눠주기
                n //= i
    if n > 1: # n도 포함되어야 하므로
        result.append(n) # 넣어주기
    return result

T = int(sys.stdin.readline())
for case in range(1, T+1):
    A, B, N = map(int, sys.stdin.readline().split())
    x, result_A, result_B = prime(N), A-1, B # A 직전까지를 빼줘야하니 A-1
    for i in range(1, len(x)+1): 
        for comb in combinations(x,i): # 소수 조합에 대해서
            m = 1 # 포함 배제의 원리를 위한 나누기용 (아래는 포함 배제 원리)
            for j in comb:
                m *= j
            if i % 2 :
                result_A -= (A-1)//m
                result_B -= B//m
            else :
                result_A += (A-1)//m
                result_B += B//m
    
    print(f'Case #{case}: {result_B-result_A}')