[백준 파이썬] 1644 소수의 연속합

[백준 파이썬] 1644 소수의 연속합

문제

하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다.

 

하지만 연속된 소수의 합으로 나타낼 수 없는 자연수들도 있는데,20이 그 예이다 7+13을 하면 20이 되기는 하지만 두수는 연속된 소수가 아니기에 적합한 표현이 아니다. 한 소수는 반드시 한번만 사용할수 있다.

 

 

입력

첫째 줄에 자연수 N이 주어진다 

출력

주어진 N을 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 출력한다.

 

풀이

소수를 찾기위해 난 에스토라체 라는 알고리즘을 사용하여 소수인 경우 1의 값을 넣어 소수인걸 나중에 확인할수 있도록 하였다.

 

시작위치를 start=1 부터 시작하게 하여 소수이면 sum에 더하게 하여 sum이 찾는값에 도달하면 경우의수 +1 ,start +1 을 하였고 더 크다면 start+1을 하여 이 과정을 start값이 찾는 수하고 같아 질때까지 반복하였다.

 

while문과 for문을 중첩해서 사용해서 시간이 좀 오래 걸리긴 하나 돌아는 간다.

다른 사람들 풀이를 보니 투포인터를 이용하여 start,end 값을 지정하여 그값 사이의 소수들의 합을 구하고 그후 

그 값이 찾는값보다 작으면 end+1,크면 start+1 을 하여 문제를 풀수 있었던것 같다.

다만 그방식은 소수를 찾고 난훈 그 소수를 따로 리스트에 저장해야하기에 최악의 조건에서는 걸리는 시간은 내가 한 풀이하고 별반 차이가 없지만 일반적인 조건에서는 내가 작성한 코드보다는 빠르게 돌아간다.

코드

n=int(input())

array=[1]*(4000001)
array[0]=0
array[1]=0

#소수 찾기위한 에스토라체
for i in range(2,len(array)):
    if array[i]==1:
        for j in range(2*i,len(array),i):
            array[j]=0

sum=0 #합을 저장할 변수
start=1 #시작위치
count=0 #경우의 수 
while(start<=n):
    if array[start]==1:
        for i in range(start,len(array)):
            # 소수인지 확인 하고 소수 이면 더한다
            if array[i]==1: 
                sum+=i
            #더한 최종값이 찾는값하고 같으면 count를 1 올린다
            #시작위치를 +1한다
            if sum==n:
                count+=1
                sum=0
                start+=1
                break
            #더한 최종값이 찾는값보다 크다면 초기화 하고
            #시작위치를 더한다
            if sum>n:
                sum=0
                start+=1
                break
    #소수가 아닌경우 시작위치를 +1한다
    else:
        start+=1



print(count)

결과