[파이썬/python] 백준 1816 - 암호키

 

---

문제

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

---

문제 설명

1. 어떤 수 S가 주어진다.
2. S의 모든 소인수가 10^6보다 크다면 그 수는 적절한 암호키이다. 그렇지 않은 경우는 적절하지 않은 암호 키이다.
3. 적절한 암호키는 "YES", 그렇지 않으면 "NO"를 출력한다.

---

풀이

S의 모든 소인수가 $10^6$보다 커야하므로 S를 $10^6$보다 같거나 작은 수로 나누었을 때 0이 나오는 수가 존재한다면, 적절한 암호키가 될 수 없다. S는 최대 10이므로 $10 * 10^6 = 10^7$회로 연산이 가능하다. 해당 문제의 시간제한인 2초($O(10^8)$)에 충분히 여유로운 시간이다.

 

1. S를 입력받는다.
2. S를 $10^6$보다 같거나 작은 수로 나눈다.
3. 1 S % i == 0 이라면 해당 수는 암호키에 적합하지 않다. flag를 0으로 초기화하고 탐색을 종료한다.
4. 모든 수를 탐색하고 flag = 1이라면 "YES" flag = 0이라면 "NO"를 출력한다

---

코드

import sys
input = sys.stdin.readline

for _ in range(int(input())):
    num = int(input())
    flag = 1
    for i in range(2, 10**6+1):
        if num % i == 0:
            flag = 0
            break
    print("YES") if flag else print("NO")

 

---

시간복잡도

• 최악일 경우 N = 10이다. 따라서 $10 * 10^6 = 10^7$이므로 약 $O(10^7)$의 시간복잡도를 가진다.