1016번 - 제곱 ㄴㄴ 수
질문들 보면 max~min 사이의 제곱수로 제곱 ㄴㄴ 수를 판별할 때 시간초과가 발생하기 때문에
에라토스테네스의 체를 이용해서 소수의 제곱수로만 판별하면 된다는데. 왜 소수의 제곱수로만 판별해도 되는거죠?
이유가 뭔지 알 수 있을까요?
소수의 제곱수집합과 모든 수들의 제곱수집합하고 비교해보세요.
댓글을 작성하려면 로그인해야 합니다.
gkfkagkfka12 6년 전
질문들 보면 max~min 사이의 제곱수로 제곱 ㄴㄴ 수를 판별할 때 시간초과가 발생하기 때문에
에라토스테네스의 체를 이용해서 소수의 제곱수로만 판별하면 된다는데. 왜 소수의 제곱수로만 판별해도 되는거죠?
이유가 뭔지 알 수 있을까요?