동백 // 백준 파이썬 2581번 소수

반응형

 

소수 출처

---

---

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	128 MB	60861	23360	20107	39.117%

---

문제

---

자연수 M과 N이 주어질 때 M이상 N이하의 자연수 중 소수인 것을 모두 골라 이들 소수의 합과 최솟값을 찾는 프로그램을 작성하시오.

예를 들어 M=60, N=100인 경우 60이상 100이하의 자연수 중 소수는 61, 67, 71, 73, 79, 83, 89, 97 총 8개가 있으므로, 이들 소수의 합은 620이고, 최솟값은 61이 된다.

입력

---

입력의 첫째 줄에 M이, 둘째 줄에 N이 주어진다.

M과 N은 10,000이하의 자연수이며, M은 N보다 작거나 같다.

출력

---

M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다.

단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다.

예제 입력 1

---

60 100

예제 출력 1

---

620 61

예제 입력 2

---

64 65

예제 출력 2

---

-1

내 코드( 시간 초과ㅠ)

import sys

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

# 소수 담을 리스트
Sosu = []


for i in range(M, N+1):
    # 약수들을 담을 리스트
    div = []

    # 1부터 i까지 나누어 지는 수들의 갯수가 2개 이상이거나 이하면, 소수가 아니다.
    for j in range(1, i+1):
        if i % j == 0:
            div.append(j)
    if len(div) == 2:
        Sosu.append(i)



if len(Sosu) == 0:
    print(-1)
else:    
    print(sum(Sosu))
    print(min(Sosu))

정답 코드

M = int(input())
N = int(input())

# 반복문 range만큼 리스트를 False로 가득 채움
check = [False for _ in range(N+1)]

# 에라토스테네스의 체를 사용하여 소수를 구해놓기
for i in range(2, int(N**0.6)):
    # 만약 check[i]가 False면 
    if check[i] == False:
        # 소수에 해당하지 않는 부분은 True로 체크해줌
        # ex) 4, 6, 8 etc....
        for j in range(2 * i, N + 1, i):
            check[j] = True


ans = []

for i in range(M, N + 1):
    #만약 i가 2보다 크거나 같으면(1은 소수가 아니기에)
    if i >= 2:
        # 만약 check[i]가 False라면, 즉 소수라면
        if check[i] == False:
            ans.append(i)


if len(ans) == 0:
    print(-1)
else :
    print(sum(ans))
    print(min(ans))