[백준(BOJ)] 1644번 : 소수의 연속합 - PYTHON[파이썬]

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

1644번: 소수의 연속합

 

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 수학
• 정수론
• 두 포인터
• 소수 판정
• 에라토스테네스의 체

---

 

⊙ 문제 접근 과정

 

에라토스테네스의 체 알고리즘으로 소수로 이루어진 리스트를 먼저 만들어준다.

투 포인터 알고리즘으로 값을 찾아준다.

 

1. n 입력
2. 에라토스테네스의 체 알고리즘으로 prime_num이라는 소수로 이루어진 리스트 생성
3. 값을 찾기 위해 반복문을 돌려준다. (투 포인터 알고리즘)
4. 값이 같으면 count up
5. 작으면 end 증가
6. 크면 start 증가

---

 

⊙ 문제 풀이

 

n = int(input())

is_prime = [False, False] + [True] * (n-1)
prime_num=[]

for i in range(2,n+1):
    if is_prime[i]:
        prime_num.append(i)
        for j in range(2*i,n+1,i):
            is_prime[j]=False

result =0
start =0
end =0

while end<=len(prime_num):
    temp=sum(prime_num[start:end])
    if temp==n:
        result+=1
        end+=1
    elif temp<n:
        end+=1
    else:
        start+=1
    
print(result)

 

---

⊙ 결과

 

---

⊙ 마무리

 

 

파이썬으로 푸니까 너무 편하다..

 

좋아요는 로그인하지 않아도 누를 수 있습니다!