1929번) 소수 구하기

문제가 너무 쉽다 했습니다.

앞서와 같이 해결할 경우, 이중 for문의 경우의 수가 기하급수적으로 증가해 시간 초과가 나게 됩니다.

'에라토스테네스의 체'에 대한사전 지식이 필요한데,,

숫자 하나하나에 대해 1~해당 숫자까지 모두 나누어보는 것이 아니라

말 그대로 체로 거르듯이 소수가 아닌 수들을 빼 줍니다.

따라서 2의 배수, 3의 배수, ..... 을 제거해줌으로써 경우의 수를 기하급수적으로 줄여줄 수 있습니다.

저는 위 이론을 직관적으로 적용해

해당 범위만큼 배열을 만들어 모든 수들을 소수라고 가정한 후,

각 배수들을 체로 걸러주었습니다.