gkfkagkfka12   6년 전

질문들 보면 max~min 사이의 제곱수로 제곱 ㄴㄴ 수를 판별할 때 시간초과가 발생하기 때문에

에라토스테네스의 체를 이용해서 소수의 제곱수로만 판별하면 된다는데. 왜 소수의 제곱수로만 판별해도 되는거죠?

이유가 뭔지 알 수 있을까요?

rdd6584   6년 전

 소수의 제곱수집합과 모든 수들의 제곱수집합하고 비교해보세요.

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