BOJ 1816 - 암호 키

문제

세 소수의 곱으로 이루어진 암호 키 S가 주어질 때, S의 모든 소인수가 100만보다 큰지 판별하라.

입력

첫째 줄에 테스트 케이스 수 N, 이후 N줄에 각 S가 주어진다.

출력

각 S에 대해 모든 소인수가 100만보다 크면 YES, 아니면 NO를 출력한다.

예제

입력	출력
`3` `1471` `2689` `4003`	`NO` `NO` `NO`

풀이

에라토스테네스의 체로 100만 이하의 소수 목록을 구해놓고, 각 S가 이 소수 중 하나로 나누어지는지 확인한다.

2부터 100만까지 에라토스테네스의 체로 소수 목록을 생성한다
각 테스트 케이스에서 S를 소수 목록의 모든 소수로 나누어본다
어떤 소수로든 나누어지면 NO (100만 이하 소인수 존재)
모든 소수로 나누어지지 않으면 YES (모든 소인수가 100만 초과)

핵심 아이디어: 100만 이하의 소수만 미리 구하면, S에 100만 이하 소인수가 있는지를 효율적으로 판별할 수 있다.

코드

n = 1000000
a = [False, False] + [True] * (n - 1)
primes = []
 
for i in range(2, n + 1):
    if a[i]:
        primes.append(i)
        for j in range(2 * i, n + 1, i):
            a[j] = False
 
N = int(input())
for i in range(N):
    b = True
    S = int(input())
    for j in primes:
        if S % j == 0:
            b = False
    if b == True:
        print("YES")
    else:
        print("NO")

복잡도

시간: O(N * pi(10^6)) (pi: 소수 개수, 약 78498개)
공간: O(10^6)

문제