13 삐약 : 백준 1929 [C++]

이놈의 소수는 언제 끝날런지싶지만 열심히 토도도독 굴려본다

 

나름 훗 나 잘해 후후훗 하고서 토도도독 쳐 봤는데 어찌된 영문인지 한 큐에 바로 그냥 냅다 실행이 되드라.

그래서 제출을 해 봤는데 어머나 세상에

시간 초과 됐다.

 

그래서 냅다 구글에 요거 시간초과 쳐 보니까 이게 에라토스테네스의 채 라는 개념에 관련된 문제라고 하더라!

옛날에 동아리 교육할 때 얼핏 들었던 것 같은데 역시나 기억도 못하고 활용도 못하는 나의 명석한 두뇌란.

 

에라토스테네스의 체는 임의의 수 n 까지의 소수를 구하고자 할 때 2부터 n의 제곱근까지 돌며 모든 배수들을 소수에서 제외시키는 방식이다. 

 

배열로 소수를 구하는 방법이다.