백준 1644 : 소수의 연속합 with 파이썬

https://www.acmicpc.net/problem/1644

1644번: 소수의 연속합

 

1. n까지의 소수 리스트를 만들어 문제를 해결하는 경우, 시간초과됨

n=int(input())
nums=[]

for i in range(2, n+1): #소수는 2부터 n까지
    cnt=0
    for j in range(1, i+1): #i를 나누는 수는 1부터 i까지
        if i%j==0:
            cnt+=1
    if cnt==2:
        nums.append(i)

#print(nums)

result=0
summ=nums[0]
st, end=0,0
while True:
    if summ==n:
        result+=1
        summ-=nums[st]
        st+=1
    elif summ > n:
        summ-=nums[st]
        st+=1
    else :
        end+=1
        if end==len(nums) :break  #소수의 갯수와 같아질때 반복문 탈출
        summ+=nums[end]

print(result)

 

 

2. 에라토스테네스의 체를 통해 소수 구하기

# 포인트

1. 소수의 배수는 소수가 아니기 때문에 그것들을 제거하는 방법

2. range(2, int(n**0.5)+1)을 통해 짝이 있는 약수구조는 이미 소수가 아니기 때문에 탐색범위에서 제외

# 에라토스테네스의 체를 이용한 n까지의 소수 구하기
n=int(input())
prime=[False, False]+[True for _ in range(n-1)] # 0과 1은 소수가 아니므로 False처리
nums=[] # 소수 리스트
for i in range(2, int(n**0.5)+1):
    prime[2*i::i]=[False]*((n-i)//i)
for i in range(n+1):
    if prime[i]:
        nums.append(i)

result=0
summ=0
st, end=0,0
while True:
    if summ==n:
        result+=1
        summ-=nums[st]
        st+=1
    elif summ > n:
        summ-=nums[st]
        st+=1
    else :
    	if end==len(nums) :break
        summ+=nums[end]
        end+=1
        
print(result)