[백준] 소수(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이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다.

 

✨ 풀이 과정 (1)

---

❓이 문제의 지문을 천천히 읽어본 후 이중 for문을 통해서 풀어야겠다는 아이디어가 떠올랐다.
→ ✅소수인 경우 이들의 합을 구할 demical 배열에 추가해주고 아니면 제외한다. 그 후 demical 배열에 아무것도 없는 경우,  -1을 출력하고 그 외의 경우 리스트의 모든 요소를 더하고 가장 작은 값인 0번째 값을 출력한다.

📖 풀이 방법
1. M과 N을 받는다.
2. 이중 for문을 통해 비교할 수(i)와 2부터 자기 자신까지 반복할 수(j)를 구한다.
3. j와 i가 같다면 소수이므로 decimal에 추가해준다.
4. 그렇지 않다면 i를 j에 나눈 나머지를 비교하여 나누어 떨어지면 소수가 아니게 되므로 break를 통해 빠져 나온다.
5. decimal이 false인 경우(아무 것도 없는 경우) -1을 출력하고, 그렇지 않으면 모든 리스트의 요소를 더한 값과 리스트의 0번째(가장 작은 값) 요소를 출력한다.

 

👩‍💻 최종 코드 (1)

---

# M과 N을 받는다
M = int(input())
N = int(input())

decimal = []
# 이중 for문을 통해 비교할 수(i)와 2부터 자기 자신까지 반복할 수(j)를 구한다.
for i in range(M, N+1):
	for j in range(2, i+1):
        #j와 i가 같다면 소수이므로 decimal에 추가해준다.
		if j == i:
			decimal.append(i)
    	#그렇지 않다면 i를 j에 나눈 나머지를 비교하여 나누어 떨어지면 소수가 아니게 되므로 break를 통해 빠져 나온다.
		if i % j == 0:
			break

#decimal이 false인 경우(아무 것도 없는 경우) -1을 출력하고, 그렇지 않으면 모든 리스트의 요소를 더한 값과 리스트의 0번째(가장 작은 값) 요소를 출력한다.
if not decimal:
	print(-1)
else:
	print(sum(decimal))
	print(decimal[0])

 

✨ 풀이 과정 (2)

---

이렇게 코드를 제출하고 알고리즘 스터디를 통해 피드백을 받던 도중 에라토스테네스의 체라는 개념을 알게 되었다.

에라토스테네스란?
가장 대표적인 소수(Prime Number) 판별 알고리즘으로 대량의 소수들을 빠르고 정확하게 구해야할 때 아주 유용한 알고리즘이다.

 

💡예를 들어, 1부터 25까지 판별한다고 생각해보자.

 

1. 2차원 배열을 생성해서 값을 초기화한다.

2. 2부터 시작해서 특정 숫자의 배수에 해당하는 숫자들을 모두 지운다.

• 2의 배수 지우기

• 3의 배수 지우기

• 이미 지워진 숫자의 경우 건너뛰기

• 2부터 시작하여 남아있는 숫자들을 출력하기

✨ 출력 값: 2, 3, 7, 11, 13, 17, 19, 23

이 개념을 사용하여 문제를 풀면 시간복잡도를 줄일 수 있다.

 

👩‍💻 최종 코드 (2)

---

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

is_prime = [True] * (N + 1)
is_prime[0] = is_prime[1] = False

for i in range(2, int(N**(1/2)) + 1):
    if is_prime[i] == False:
        continue
    
    for j in range(i * i, N + 1, i):
        is_prime[j] = False
        

primes = [x for x in range(M, N + 1) if is_prime[x] == True]
if len(primes) == 0:
    print(-1)
else:
    print(sum(primes), primes[0])