10. Python(소수 찾기)

[toc]

벌집

문제

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

---

제출

m = int(input())
n = int(input())
sosu_list = []

for i in range(m, n+1):
    cnt = 0
    if i < 2:
        continue
    for j in range(1, int(i**0.5) + 1): # 만약 i가 13일 때 1 부터 2.xxxx(루트 13)까지 루프를 돌리는 것으로 만약 소수이면 1하고만 나눠떨어짐 그래서 cnt += 2를 해주는 갓
        if i % j == 0:
            if j == i // j: # 소수가 아닌 것
                cnt += 1
            else: # 소수인 것
                cnt += 2 # 1하고만 나눠 떨어지는 수는 소수이기 때문에 2를 더함
    if cnt == 2:
        sosu_list.append(i)
        
if sosu_list:
    print(sum(sosu_list)) # 소수인 것의 합
    print(min(sosu_list)) # 소수인 것 중 최소값
else:
    print(-1) # 소수가 없을 때

# 입력
60
100

# 출력
620
61

---

인사이트

• m과 n 사이에 존재하는 모든 소수를 찾아 그 합을 구하고, 최소값을 출력하되, 소수가 없을 경우 -1을 출력하는 프로그램

• m과 n 사이의 소수를 리스트에 저장한 후, 해당 리스트의 합(sum)과 최소값(min)을 출력하는 방법을 생각했음

• 자연수 n의 약수 중 1과 n을 제외한 나머지 약수는 n의 제곱근보다 항상 작다는 점을 확인하고, 이를 활용해 반복문의 크기를 줄여 메모리와 제한 시간 문제를 해결했음

  for j in range(1, int(i**0.5) + 1): # j의 범위를 1부터 제곱근 i까지 설정함
     if i % j == 0:
          if j == i // j: # 소수가 아닌 것
              cnt += 1
          else: # 소수인 것
              cnt += 2