[프로그래머스][level 1] 소수 찾기

 

문제

https://programmers.co.kr/learn/courses/30/lessons/12921

주의할 점

 - 효율성 생각 : O(N^2)는 효율성 통과가 안됨. 

필요 지식

 - 에라토스테네스의 체 

• 소수가 아닌 것을 거르는 체
• 소수가 아닌 것은 소수의 배수로 표현될 수 있다.
• ex) 4 = 2+2, 6 = 2+2+2, 9 = 3+3+3 등등
• 즉, 0~n까지 들어있는 배열([0,1,2,3,4,5,6,...])에서 2부터 전체를 조회하며 소수가 아닌 수는 0으로 만들어 버림 ([0,1,2,3,0,5,0,7,0,0,0,11,...])
• 조회할 때, 이미 배열에서 0이 되어버린 것은 소수가 아닌 것이므로 확인할 필요가 없다.

코드

효율성 실패 코드