[파이썬] 백준 7501번 - Key 풀이

https://www.acmicpc.net/problem7501
티어: 플래티넘 1

 

 

 

 

로직

입력으로 주어지는 두 정수 A, B 사이에 있는 Key값을 전부 출력해주면 되는 간단한 문제입니다.

 

Key의 조건

1. 홀수 정수

2. (K-1)! 가 K² 으로 나누어 떨어지지 않는다.

 

A, B 사이의 모든 정수에 대해 팩토리얼 값을 구하고, 직접 나누어 보면 당연히 시간초과가 날겁니다.

Key값의 조건을 조금 더 살펴보면 모든 홀수 소수가 Key에 해당된다는건 어렵지 않게 찾을 수 있습니다.

K가 소수라면 (K-1)!에 K가 포함되어 있지 않으니, 나누어 떨어지지 않기 때문입니다.

 

그런데, 예제를 보면 소수가 아닌 9도 Key에 포함되어있는걸 볼 수 있습니다.

처음에는 조건을 잘못 찾은 줄 알았는데, 소수가 아닌 Key값은 9가 유일합니다.

 

A부터 B 사이의 모든 홀수 정수에 대해 소수 또는 9인지 검사하고, 맞다면 배열에 추가하는 식으로 구현했습니다.

 

A, B의 범위가 10¹⁸까지로 매우 크므로 밀러-라빈 소수판별법을 사용해 소수인지 검사해줍니다.