백준[16464] 소수의 연속합 (파이썬 풀이)

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

1644번: 소수의 연속합

 

내가 한 풀이 1 (시간 초과)

def is_prime(x):
    for i in range(2,x):
        if x%i==0:
            return False
    return True

n=int(input())
arr=[]
for i in range(2,n+1):
    if is_prime(i):
        arr.append(i)
    else:
        pass
start,end=0,0
com=0
answer=0
while True:
    if com>n:
        com-=arr[start]
        start+=1
        
    elif com==n:
        answer+=1
        com-=arr[start]
        start+=1
    elif end==len(arr):
        break
    else:
        com+=arr[end]
        end+=1
    
print(answer)

 

문제점 : 입력값의 범위가  4,000,000까지 였기때문에 for 문을 해 n을 하나씩 소수 판별하면 시간 초과가 발생한다.

 

해결 방안: 시간 초과를 해결하기 위해서 에라토스테네스의 체를 이용했다.

 

에라토스테네스의 체란?

소수를 판별하는 알고리즘으로 어떤 수를 판별 하고 그 수의 배수를 모두  지워 많은 양의 소수를 판별해야 할 때 사용한다. 시간 복잡도는 O(N*log(logN)) 이다.

 

내가 한 풀이 2 (에라토스테네스의 체 이용한 최종 풀이)

# 에라토스테네스의 체 알고리즘
n=int(input())
arr=[False,False]+[True]*(n-1) #앞에 두개는 0과 1
primeList=[]
for i in range(2,n+1): #2부터 판별한다.
    if arr[i]:
        primeList.append(i)
        for j in range(2*i,n+1,i): #해당 수의 배수를 모두 False로 갱신한다.
            arr[j]=False
 
start,end=0,0
com=0
answer=0
while True:
    if com>n:
        com-=primeList[start]
        start+=1
        
    elif com==n:
        answer+=1
        com-=primeList[start]
        start+=1
    elif end==len(primeList):
        break
    else:
        com+=primeList[end]
        end+=1
    
print(answer)