[백준] 2581: 소수 (Python)

• https://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을 출력한다.

 

입출력 예제

입력	출력
60 100	620 61
64 65	-1

 

풀이

1) 에라토스테네스의 체 사용

입력을 받고 에라토스테네스의 체로 해당 범위 내의 소수를 구함

(m부터 n까지의 소수만 구하고 싶었는데 에라토스테네스의 체 자체가 2부터 시작해야 성립하는 구조라서 그럴 수 없었음)

완성된 체를 보고 m부터 n까지의 수에 대해 소수면 배열에 추가

배열이 비었는지 아닌지에 따라 합/최솟값 또는 -1 출력

• 에라토스테네스의 체
  • 0과 1은 소수가 아니라고 미리 초기화해주어야 함
  • 2부터 루트 n까지 (약수가 될 수 있는 수의 범위)
  • 해당 수가 소수라면 해당 수*2부터 n까지 배수를 모두 소수가 아닌 수로 처리

import sys
input = sys.stdin.readline
m = int(input())
n = int(input())
def sieve(n):
	decimal = [True] * (n+1)
	decimal[0] = decimal[1] = False
	for i in range(2, int(n ** 0.5) + 1):
		if decimal[i]:
			for j in range(i*2, n+1, i):
				decimal[j] = False
	return decimal
dec = sieve(n)
ans = []
for i in range(m, n+1):
	if dec[i]:
		ans.append(i)
if ans:
	print(sum(ans))
	print(min(ans))
else:
	print(-1)

메모리: 31256 KB / 시간: 44 ms

 

2. 범위 안의 모든 수(num)에 대해 2부터 루트 num까지 나눠보기

만약 약수가 있으면 break, 약수가 하나도 없으면 append

iteration을 더 많이 해서 1번보다 오래 걸림

import sys
input = sys.stdin.readline
m = int(input())
n = int(input())
arr=[]

for num in range(m ,n+1):
    if num > 1:
        is_decimal = True
        for j in range(2, int(num ** 0.5) + 1):
            if num % j == 0:
                is_decimal = False
                break
        if is_decimal:
            arr.append(num)
if len(arr)==0:
    print('-1')
else:
    print(sum(arr))
    print(min(arr))

메모리: 31256 KB / 시간: 56 ms