백준 2581 소수 - python

출처 : https://www.acmicpc.net/problem/2581

2581번: 소수

풀이 :

# 시간 초과
a = int(input())
b = int(input())

prime = []

for i in range(a,b+1):
    cnt = 0
    if i ==1 :
        continue
    for j in range(2,b+1):
        if i % j == 0:
            cnt += 1        
    if cnt == 1 :
        prime.append(i)
        
if prime == []:
    print(-1)
else:
    print(sum(prime))
    print(min(prime))

 

a = int(input())
b = int(input())

prime = []

for i in range(a,b+1):
    cnt = 0
    if i ==1 :
        continue
    for j in range(2,b+1):
        if i % j == 0:
            cnt += 1
        if cnt == 2:
            break       
    if cnt == 1 :
        prime.append(i)
        
if prime == []:
    print(-1)
else:
    print(sum(prime))
    print(min(prime))

다음 처럼 풀이를 해봤다.

이전 앞에서 풀었던 소수문제와 비슷하지만 이 문제에서는 소수의 합과 최소값 까지 구하라고 해서 리스트를 이용해서 풀이하기로 했다.

 

그래서 리스트 prime = [] 을 만들어 준다음 

** 앞 문제에서 지적해주신 류정식** 님의 말대로 range를 굳이 만까지 안잡아도 b+1이 넘어가면 어차피 의미 없으므로 range(2,b+1) 만큼 해준다.

 

그런 다음 cnt == 1 인 부분에 리스트를 추가해서 빈 리스트는 -1을 출력 그것이 아니라면 합과 최소값을 출력하게 했다. 

하지만 여기까지만 하면 시간초과에 걸렸다.

 

왜냐하면 for j in range(2,b+1) 에서 계속 무수히 cnt 를 더하는 쓸데없는 계산을 하기 때문이다.

따라서 if cnt == 2 : 일때 멈춰주는 break 를 해서 계산량을 줄였고 통과했다.