백준 / 소수의 연속합 / 1644번 / Python

*문제 출처는 백준에 있습니다.

문제 제목: 소수의 연속합 / 1644번 (골드 3단계)

문제 사이트: https://www.acmicpc.net/problem/1225

 

문제 설명

---

나의 풀이

N = int(input())

# 에라토스테네스의 체 알고리즘
isPrime = [True] * (N + 1)
isPrime[0] = isPrime[1] = False

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

# 소수 리스트
primes = [i for i in range(2, N + 1) if isPrime[i]]

count = 0
prime_len = len(primes)

for i in range(prime_len):
    result = 0
    for j in range(i, prime_len):
        result += primes[j]
        if result == N:
            count += 1
            break
        elif result > N:
            break

print(count)

---

※ 알아야 할 것

https://newkimjiwon.tistory.com/44

소수(Prime Number) 구하기 알고리즘

소수 구하는 알고리즘 중에서 배열로 저장해서 사용하는 에라토스테네스의 체를 사용해야 시간 복잡도를 줄일 수 있다.