[BOJ/Step9] 2581 : 소수 (Python)

www.acmicpc.net/problem/2581

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

 

예제 입력 1

60

100

 

예제 출력 1

620

61

 

예제 입력 2

64

65

 

예제 출력 2

-1

---

풀이

(1) m과 n 사이 숫자를 각각 소수 판별

  1. 소수면 True를, 아니면 False를 반환하는 함수 is_prime(a)

    1-1. a가 1이면 return False

    1-2. a를 2~a-1의 수로 나눴을 때 나머지가 0이 되면 return False

    1-3. a를 2~a-1의 수로 모두 나눴는데 한번도 나머지가 0이 되지 않으면 return True

  2. m과 n 사이의 소수를 저장할 리스트 mn

  3. m부터 n까지 a를 소수 판별, is_prime이 True를 반환할 때만 mn에 a 추가

  4. mn이 비어있으면 -1출력

  5. mn이 비어있지 않으면 mn의 합과 최솟값 출력

# 2581-1.py

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


def is_prime(a):
    if a == 1:
        return False
    for j in range(2, i):
        if i % j == 0:
            return False
    return True


for i in range(m, n+1):
    if is_prime(i):
        mn.append(i)

if not mn:
    print(-1)
else:
    print(sum(mn))
    print(min(mn))

 

(2) 1~10000까지의 수를 미리 소수 판별 후 입력받아 확인
  1. prime 리스트안에 미리 2, 3을 넣어둔다

    2. 4~10000까지의 숫자 i를 소수 판별

    2-1. i를 prime안의 숫자로 나눠 모두 0이 아닐때만 prime 리스트에 값을 추가한다

  2. m과 n 사이의 소수를 저장할 리스트 mn

  3. m부터 n까지 a가 prime 안에 존재할 때만 mn에 a 추가

  4. mn의 길이가 0이 아니면 mn의 합과 최솟값 출력

  5. mn의 길이가 0이면 -1출력

# 2581-2.py

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

prime = [2, 3]
for i in range(4, 10001):
    pp = [i % k for k in prime]
    if all(pp):
        prime.append(i)

for i in range(m, n+1):
    if i in prime:
        mn.append(i)

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