[Two pointers] BJ1644 - 소수의 연속합 python

 

문제

1644번: 소수의 연속합

1644번: 소수의 연속합

풀이

• 에라토스테네스의 체 알고리즘 + two pointer 유형
• 에라토스테네스의 체는 table을 설정함으로써 time complexity를 줄일 수 있음
• N이하의 소수 리스트를 구한 뒤 two pointer적용
• 연속된 소수 리스트는 slicing을 통해 sum이 N이 되는 경우 count++

코드

from sys import stdin

input = stdin.readline
N = int(input())
primeList = []

def main():
    count = 0

    def getPrimeList(N): # N이하의 소수 리스트 구하기
        sieve = [True] * (N+1) # 숫자를 인덱스로 취하기 위함, 모든 i를 소수로 설정(검증대상)
        m = int(N**0.5)
        for i in range(2, m+1):  # 2부터 N제곱근까지의 수까지만 검증
            if sieve[i] == True:
                for i in range(i+i,N+1,i): # i이후에 등장하는 i 배수부터 N까지 False로 전환 (i의 배수는 무조건 소수가 아니므로)
                    sieve[i] = False 
              # 나누어 떨어지면 소수아님
        return [ i for i in **range(2, N+1)** if sieve[i] == True] #체에서 True(소수)인 i만 반환
    primeList = getPrimeList(N)

    start, end = 0, 0  # 포인터 초기화
    while end <= len(primeList):  # 소수 배열을 순회해야함
        if sum(primeList[start:end]) < N:
            end += 1
        elif sum(primeList[start:end]) > N:
            start += 1
        else:  # 같은 경우
            count += 1
            end += 1
    print(count)
main()

참고사항

• list[n:n] 은 빈 리스트를 반환, sum([]) = 0
  • 리스트 슬라이싱은 리스트를 반환함.
• 에라토스테네스의 체 알고리즘으로 소수 리스트를 반환하기 위해선 table 설정이 필요
  • sieve = [True] * (N+1) 형태로 초기화 (N+1은 2부터 시작하는 i를 인덱스로 그래도 사용하기위해 적용한 것)
  • 일반적인 isPrime소수 판별 함수를 map으로 적용하는 것은 시간복잡도가 증가.
• while end <= len(primeList) 조건문에서 end포인터는 슬라이싱으로 -1되므로 len(primeList)값을 포함해야함.
• 에라토스테네스의 체
  • sieve = [True] * (N+1)초기화 (초기에 모든 i가 소수인 것으로 간주)
  • < for i in range(2,m+1) > : 2부터 m = int(math.sqrt(N))까지 i를 순회
    • sieve[i] == True인 경우, for i in range(i+i, N+1, i): sieve[i] = False
    • i이후의 모든 i배수에 대해 False처리(소수에서 제외)
  • sieve리스트에서 True인 i만 반환 (2이상 N이하) ⇒ 소수 리스트 반환

 

Reference

https://this-programmer.tistory.com/409

에라토스테네스의 체 (소수구하기. 파이썬)