[구현] 소수의 연속합 - 소수 판별 (에라토스테네스의 체)

이 문제의 핵심은 소수를 어떻게 효율적으로 찾을것인가 문제였던거 같다..

✅ 에라토스테네스의 체

알고리즘 설명

🔹2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
🔹2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)자기 자신을 제외한 2의 배수를 모두 지운다.
🔹남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)자기 자신을 제외한 3의 배수를 모두 지운다.
🔹남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)자기 자신을 제외한 5의 배수를 모두 지운다.
🔹남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)자기 자신을 제외한 7의 배수를 모두 지운다.
🔹위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다. (보라색)

 

🔴 틀린 코드

에라토스테네스의 체 알고리즘과는 조금 다르지만

백준 `질문 게시판`에서 코드를 참고해서 소수를 구하기는 했는데 IndexError가 났다.

#소수의 합으로 나타낼 수 있는 경위의수
import sys
n = int(sys.stdin.readline().rstrip())
#소수 찾아서 배열에 저장 -> 이게 시간초과의 원인이였음 소수를 어떻게 효율적으로 찾을것인가...
primes = [False, False] + [True] * (n-1)
data = []
for i in range(2, n+1):
    if primes[i]:
        data.append(i)
       
        j = 2
        while i*j <= n:
            primes[i*j] = False
            j += 1


start, end = 0, 0
total = data[start]
cnt = 0
while start <= end and end < len(data):
  if total == n: #start 포인터 이동해서 다른 구간도 가능한지 검사
    total -= data[start]
    start += 1
    cnt += 1
  elif total < n:
    end += 1 #end 포인터가 가리키는 요소도 포함
    if end >= len(data):
      break
    total += data[end]
    
  elif total > n:
    total -= data[start]
    start += 1
    
print(cnt)

 

🟢정답 코드

while 반복문 조건과 total 값을 0으로 초기화했더니 IndexError 해결...

#소수의 합으로 나타낼 수 있는 경위의수
import sys
n = int(sys.stdin.readline().rstrip())
#소수 찾아서 배열에 저장 -> 이게 시간초과의 원인이였음 소수를 어떻게 효율적으로 찾을것인가...
primes = [False, False] + [True] * (n-1)
data = []
for i in range(2, n+1):
    if primes[i]:
        data.append(i)
       
        j = 2
        while i*j <= n:
            primes[i*j] = False
            j += 1

start, end = 0, 0
total = 0
cnt = 0
while start <= end:
  if total == n: #start 포인터 이동해서 다른 구간도 가능한지 검사
    total -= data[start]
    start += 1
    cnt += 1
  elif total < n:
    if end >= len(data):
      break
    total += data[end]
    end += 1
    
  elif total > n:
    total -= data[start]
    start += 1

print(cnt)

---

ref: https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4