dpwns1234   1년 전

1 부터 1000000까지 엄청나게 많은 소수가 있는데 그걸 시간초과없이 출력하는게 가능합니까?? 소수만 찾은다음 for문으로 입력된 값만 출력해도 시간초과 뜰 것 같은데...ㅜㅜㅜ

djm03178   1년 전

질문 게시판의 다른 질문들을 보고 아 저렇게도 할 수 있구나! 하는 걸 꺠달아보세요.

surung9898   1년 전

소수 판정에 있어서, 어떤 자연수 n을 판정하는 기준으로 보통 'n이 2부터 sqrt(n)까지의 수 중 하나로 나누어 떨어지는가'를 보통 채택합니다. 예시로, 32가 소수인지를 판정할 때에는 32를 2부터 5까지만 나누어 볾으로써 소수를 판정할 수 있습니다.

간략하게 설명드리자면, 32의 약수는 각각 1 2 4 8 16 32이므로, 32를 4를 나누어 보는 것과 8을 나누어 보는 것에는 차이를 가지지 않는다는 것입니다.


결과적으로, 어떤 수 n을 판정하기 위해서, 반복문을 2부터 sqrt(n)까지만 돌면서 나누어떨어지는 수가 나올 시 바로 반복문을 종료하시면 시간을 줄일 수 있을 것입니다.

atomzeno   1년 전

위의 방법도 있고

에라토스테네스의 체를 사용해도 됩니다

댓글을 작성하려면 로그인해야 합니다.