[BOJ/Python] 1644 소수의 연속합

문제

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

1644번: 소수의 연속합

코드

풀이

소수만 arr에 저장하기 위해 입력받은 N만큼의 리스트를 모두 True로 저장한 뒤 2부터 곱해지는 수들을 모두 False로 만든다. 이때 j를 2부터 하나씩 더하면서 곱하므로 N의 제곱근까지 범위로 설정하면 N까지 모든 소수를 찾아낼 수 있다.

True로 저장된 소수를 result 안에 넣고 2부터 곱해지는 수를 False로 저장했으므로 True로 남아있는 0과 1을 빼낸다.

그 이후 투포인터를 실행하는데 L부터 R까지의 합이 N과 같으면 cnt+=1하고 합이 더 크면 L을 옮겨서 sum의 범위를 줄이고 합이 더 작으면 R을 옮겨서 sum의 범위를 늘린다.

모든 실행마다 R의 길이와 result의 길이를 비교하여 R이 result의 길이보다 커지면 while을 빠져나와 cnt를 출력한다.

이때 sum의 값이 N보다 작을 때만 R+=1을 하므로 R의 길이가 result의 길이보다 커지면 sum이 더이상 N이 될 수 없다.