(BOJ)-1816, Python

문제 요약

출처: (BOJ)1816 - 암호키

N개의 키가 주어졌을 때, 각 키가 적절한 암호키인지 판별하여 “YES” 또는 “NO”를 출력하는 문제이다.
암호키의 조건은 다음과 같다:

• 2부터 1,000,000 사이의 어떤 수로도 나누어 떨어지지 않는 경우 “YES”
• 나누어 떨어지는 경우 “NO”

접근 과정

1. 완전탐색 접근

처음에는 2부터 key까지 반복하면서 소수를 판별해야겠다고 생각했다.
하지만 주어질 수 있는 키의 범위를 보면 10^12 ~ 10^18 이기에 완전탐색으로 접근하지만 너무 무식한 것 같아서 문제를 다시 보았다.

2. 문제 조건 활용

문제를 다시 읽어보니 중요한 힌트가 있었다:
만일 S의 모든 소인수가 10^6보다 크다면 그 수는 적절한 암호 키이고, 그렇지 않은 경우는 적절하지 못한 암호 키가 된다.
즉, 키가 1,000,000 이하의 소인수를 갖지 않으면 “YES”를 출력하면 된다는 말이다.

따라서 반복문을 활용해 2부터 1,000,000까지만 검사하는 방식으로 해결하는 방법으로 진행했다..!!

코드 구현

n = int(input())  # 키의 개수 입력

for _ in range(n):
    key = int(input())  # 각 키 입력
    
    for i in range(2, 1000001):  # 2부터 1,000,000까지 반복
        if key % i == 0:  # 소인수가 10^6보다 작을 경우 NO 출력
            print("NO")
            break
    else:  # 반복문이 break 없이 종료된 경우 YES 출력
        print("YES")

회고

문제를 똑바로 읽고 이해하려는 습관을 가지자..