백준 #1816

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

1816번: 암호 키

 

• 나의 풀이

def rtn_primes(num):
    """
    input(비밀번호)에 대한 모든 소인수를 요소로 갖는 리스트 반환 
    """
    primes = []
    i = 2
    while i == num:
        if num % i == 0:
            primes.append(i)
        i += 1
    return primes

# 주어진 횟수를 요소의 길이로 갖는 비밀번호 리스트 생성
num = int(input())
password_list = []
for i in range(num):
    password = int(input())
    password_list.append(password)

# 비밀번호별로 소인수의 최솟값이 1000000이 넘는지 판별 
for i in password_list:
    primes = rtn_primes(i)
    if min(primes) > 1000000:
        print("YES")
    else:
        print("NO")

 

• 모범답안

tc = int(input())
for _ in range(tc):
    num = int(input())

    for i in range(2, 1000001):
        if num % i == 0:
            print("NO")
            break
        if i == 1000000:
            print("YES")

 

• 고찰

• 주어진 비밀번호에 대한 모든 소인수를 가지고 있을 필요가 없었다. 장황하게 풀어서 timeout이 떴다.
• 모든 수는 자신을 소인수로 가지므로 2부터 1000000사이의 소인수를 가지고 있지 않는 조건을 통과 후 i가 1000000에 도달할 수 있는지만 확인하면 모든 소인수의 최솟값이 1000000 이상임을 만족하는 비밀번호이다.