16441 [Alogorithm - Python(파이썬)] 백준 1644 - 소수의 연속합 (투 포인터, 구간 합, 에라토스테네스의 체) https://www.acmicpc.net/problem/1644 이 문제는 다른 구간 합 문제와 동일하지만, 연속된 수가 아닌 연속된 소수의 구간 합을 구하는 문제이다. 때문에 연속된 소수를 구해야 했고, 이전에 풀었던 에라토스테네스의 체 개념을 적용해서 통과할 수 있었다. 에라토스테네스의 체란 무엇인가? 개념부터 잡고 가자. - 에라토스테네스가 만든 소수를 찾는 방법- 마치 체로 치듯이 수를 걸러낸다고 하여 에라토스테네스의 체라고 부른다. ex) 100 이하의 자연수 중에서 소수를 찾아라. 1. 1부터 100까지 숫자를 쓴다. 2. 소수도 합성수도 아닌 1을 제거한다. 3. 2를 제외한 2의 배수를 제거한다. 4. 3을 제외한 3의 배수를 제거한다. * 4는 제거할 필요 없다. (2의 배수에서 이미 .. 2024. 8. 19. 이전 1 다음
