[백준] 2501 : 약수 구하기 (Python/파이썬)

문제 링크

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

문제

자연수 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을 출력한다.

예제

입력

60
100

출력

620
61

입력

64
65

출력

-1

---

정답 및 풀이

m = int(input())
n = int(input())
cnt=0
arr=[]
for i in range(m,n+1):
    if i > 1 :
        for j in range(2, int(i**0.5)+1):
            if i % j == 0 :
                break
        else:
            arr.append(i)
            cnt += i
if len(arr) <= 0 :
    print(-1)
else:
    print(cnt)
    print(min(arr))

1. m = int(input())
   • 첫 번째 줄에서 시작값 m을 입력받아 정수로 변환합니다.
2. n = int(input())
   • 두 번째 줄에서 끝값 n을 입력받아 정수로 변환합니다.
3. cnt = 0
   • 소수들의 합을 저장할 변수를 0으로 초기화합니다.
4. arr = []
   • 소수들을 저장할 리스트를 초기화합니다.
5. for i in range(m, n + 1):
   • m부터 n까지 모든 정수 i를 하나씩 검사합니다.
6. if i > 1:
   • 1은 소수가 아니므로, 1보다 큰 수만 검사합니다.
7. for j in range(2, int(i ** 0.5) + 1):
   • i가 소수인지 판별하기 위해 2부터 √i까지만 나누어 봅니다.
   • 제곱근까지만 확인해도 효율적으로 소수를 판별할 수 있습니다.
8. if i % j == 0:
   • i가 j로 나누어 떨어진다면 i는 소수가 아닙니다.
9. break
   • 약수가 발견되면 더 이상 검사할 필요가 없으므로 반복을 종료합니다.
10. else:
    • for문이 break 없이 끝났다면 i는 소수이므로 else문 실행됩니다.
11. arr.append(i)
    • 소수로 판별된 i를 리스트에 추가합니다.
12. cnt += i
    • 소수의 합을 구하기 위해 cnt에 더합니다.
13. if len(arr) <= 0:
    • 소수 리스트가 비어 있다면 (소수를 한 개도 찾지 못했다면) 참이 됩니다.
14. print(-1)
    • 소수가 없을 경우 문제 조건에 따라 1을 출력합니다.
15. else:
    • 소수가 하나라도 존재할 경우 실행됩니다.
16. print(cnt)
    • 찾은 모든 소수의 합을 출력합니다.
17. print(min(arr))
    • 찾은 소수들 중 가장 작은 소수를 출력합니다.

---