[프로그래머스] 소수 찾기(with python)
처음에 이중for문으로 해결하려다 보니 n이 클 때 시간복잡도가 크게 증가하여 시간초과로 통과하지 못했다. 힌트를 얻기 위해 질문하기에 들어가봤다. '에라토스테네스의 체' 라는 개념을 사용해야 한다. 그리스의 수학자이자 지리학자인 에라토스테네스가 고안한 소수(素數)를 찾는 방법으로, 이 방법으로 소수를 찾으려면, 2부터 시작해 자연수를 차례로 쓴 다음, 2 이외의 2의 배수, 3 이외의 3의 배수, 5 이외의 5의 배수의 순서로 수를 지워나가 끝에 남는 수가 소수이다. [네이버 지식백과] 에라토스테네스의 체 [Eratosthenes' sieve] (두산백과) 에라토스테네스의 체 그리스의 수학자이자 지리학자인 에라토스테네스가 고안한 소수를 찾는 방법으로, 이 방법으로 소수를 찾으려면, 2부터 시작해 자연수..