[Baekjoon 21920] 서로소 평균 | Python

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

---

문제

 

주어진 수열에서 주어진 수와 서로소인 수들을 모두 고르고, 그 서로소인 수들의 평균을 구하는 문제이다.

 

---

풀이

 

수열의 길이가 500,000까지 가능하고, 주어지는 수가 1,000,000까지 가능하기 때문에 반복문을 활용하여 단순하게 접근하면 시간 초과가 날 수 있는 문제이다. 따라서 효율적으로 서로소를 구하도록 접근해야 한다.

서로소는 공약수가 1 뿐인 두 정수이다. 즉 주어진 수의 약수로 나누어 떨어지는 수가 있다면 그 수는 서로소가 될 수 없다. 또한 더 생각해본다면 약수 중 소수로만 확인해도 서로소인지 아닌지 확인할 수 있다.

따라서 주어진 정수의 약수 중 소수를 골라내야 한다. 약수를 먼저 고르는 것 보다 에라토스테네스의 체를 사용하여 소수를 먼저 고르는 것이 효율적이다.

에라토스테네스의 체를 활용해 대상 수의 제곱근까지 소수를 체크하여 소수이면서 약수가 될 수 있는 수들을 리스트로 만들어준다. 이 리스트에서 다시 약수인 수를 확인하여 리스트로 만들어준다.

이렇게 만들어진 리스트로 서로소가 될 수 있는 수열의 수들이 서로소인지 확인한다.

모든 서로소를 모두 구했다면 이 서로소들의 평균을 출력해주면 된다.

 

---

코드

 

def prime_divisors(n):
    sieve = [True] * (n + 1)
    sieve[0] = sieve[1] = False
    for i in range(2, int(n**0.5)+1):
        if sieve[i]:
            for j in range(i*i, n+1, i):
                sieve[j] = False
    primes = [idx for idx, is_prime in enumerate(sieve) if is_prime]
    prime_divs = [p for p in primes if n % p == 0]
    return prime_divs

target_n = int(input())
target_list = list(map(int, input().split()))
key = int(input())
key_div = prime_divisors(key)
ans_list = []
for target in target_list:
    check = True
    for i in key_div:
        if target % i == 0:
            check = False
            break
    if check:
        ans_list.append(target)
ans = sum(ans_list) / len(ans_list)
print(ans)