에라토스테네스의 체

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

[Gold III] https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 풀이 1 보자마자, Prefix Sum 문제라고 생각했다. 먼저 에라토스테네스의 체를 이용해 입력값인 N까지의 수 중 소수를 구하고, 그 소수들의 리스트를 이용해 prefix sum 리스트를 만든 후, Two Pointer 기법을 이용해 부분합의 값이 N과 동일한 지 확인하는 방법. 시간은 충분했으나, MLE. (Memory Limit Exceed.) N = int(input()) nums = {i: 0 for i in range(2, N+1)} # 에라토스테네스의 체 for i in nums: ..