[백준 알고리즘/Python3] 1929 에라토스테네스의 체
알고리즘/백준알고리즘·2021. 10. 31.
문제이해 에라토스테네스의 체에 대한 설명은 위키백과에도 잘 나와있다. -> https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4 에라토스테네스의 체는 고전적인 방법이지만 소수 판정 알고리즘에서 빠질 수 없으며 소수를 이해하기 위한 최고의 알고리즘이라고 생각된다. 가볍게 설명하자면 1. 소수면 체크한다. 2. 체크한 값의 배수는 모두 소수판별에서 제외한다. 3. 이 과정을 반복한다. 코드 m,n = map(int, input().split()) count = 0 a = [False, False] + [True] * (n-1) #에라토스테네스의 체로 리스트a..