백준 2581번

직전 문제에 이어 또 시간 초과 에러가 발생했다.

 

처음 제출한 코드는 다음과 같다.

import sys

M = int(sys.stdin.readline())
N = int(sys.stdin.readline())

p = []
min = 0

for i in range(M, N+1):
    if i == 1:
        continue
    
    f = 0

    for j in range(i):
        if j+1 == 1:
            continue
        elif j+1 == i:
            continue
        elif i % (j+1) == 0:
            f += 1
    
    if f == 0:
        p.append(i)

if len(p) == 0:
    print(-1)
else:
    print(sum(p))
    print(p[0])

 

역시나 반복문이 문제가 되었을 것이다.

 

for j in range(i): 반복문에서 사실 약수가 2개가 넘어가면 이미 소수가 아니므로 그 이상의 확인을 위한 반복은 무의미하다.

 

약수의 개수가 2개를 넘어갔는지 확인하는 조건문을 추가해 수정하였다.

import sys

M = int(sys.stdin.readline())
N = int(sys.stdin.readline())

p = []
min = 0

for i in range(M, N+1):
    if i == 1:
        continue
    
    f = 0

    for j in range(i):
        if j+1 == 1:
            continue
        elif j+1 == i:
            continue
        elif i % (j+1) == 0:
            f += 1
            if f > 0:
                break
    
    if f == 0:
        p.append(i)

if len(p) == 0:
    print(-1)
else:
    print(sum(p))
    print(p[0])

 

무의미한 반복이 이루어지지 않도록 주의하기!

 

※ 이 문제 좀 더 효율적으로 다시 풀어보자