문제.
풀이.
에라토스테네스의 체를 이용하여 소수를 구하고 부분합 을 이용하여 소스코드를 작성하면 된다.
https://turret1234.tistory.com/141
백준 1912 연속합 - 파이썬
문제. 풀이. dp[0]에 arr[0]의 값을 넣어준 뒤 연속으로 더하는게 더 큰 숫자면 더한 값을 dp에 넣어주고 더하지 않고 새로운 숫자를 넣어주는게 값이 더 크다면 그 값을 dp에 넣어주는 방식으로 계속
turret1234.tistory.com
에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전
수학에서 에라토스테네스의 체는 소수를 찾는 방법이다. 고대 그리스 수학자 에라토스테네스가 발견하였다. 알고리즘[편집] 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서
ko.wikipedia.org
소스코드.
import sys
# 에라토스 테네스의 체
def prime_number(n):
numbers = [True for i in range(n)]
m = int(n ** 0.5)
for i in range(2, m+1):
if numbers[i]:
for j in range(i+i, n, i):
numbers[j] = False
return [i for i in range(2, n) if numbers[i] == True]
input = sys.stdin.readline
n = int(input())
prime= prime_number(n+1)
start, end , result = 0, 1, 0
while end <= len(prime):
temp = sum(prime[start:end])
if temp == n:
result += 1
end +=1
if temp < n:
end += 1
else:
start += 1
print(result)
'프로그래밍 > 백준' 카테고리의 다른 글
백준 14002 가장 긴 증가하는 부분 수열 4 - 파이썬 (0) | 2021.08.02 |
---|---|
백준 12852 1로 만들기 2 - 파이썬 (0) | 2021.08.02 |
백준 11066 파일 합치기 - 파이썬 (0) | 2021.07.29 |
백준 9370 미확인 도착지 - 파이썬 (0) | 2021.07.29 |
백준 15654 N과 M(5) - 파이썬 (0) | 2021.07.29 |