[백준] 단계별로 풀어보기 - 9단계 4948번 베르트랑 공준

자기 자신의 수 직전까지 나누어서 확인하는 방식은 시간초과가 발생

에라토스테네스 체 란 알고리즘을 활용!

에라토스테네스 체란? 체에 걸러지듯 소수에 배수를 미리 제거하는 방식

2이라면 4, 6, 8, .... n 직전의 2배수까지

3이라면 9 15, .... n 직전의 3배수까지

여기서 6은 이미 2배수에서 걸러져서 지울 필요없다..

---

CODE

 

---

출처 : https://jason9319.tistory.com/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