에라토스테네스의 체
-
[백준] 1016번 제곱 ㄴㄴ수문제 풀이 2020. 7. 16. 19:24
1016 제곱 ㄴㄴ 수 문제어떤 수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min과 max를 포함한 사이에 제곱ㄴㄴ수가 몇 개 있는지 출력한다. 입력첫째 줄에 min과 max가 주어진다. min은 1보다 크거나 같고, 1,000,000,000,000보다 작거나 같은 자연수이고, max는 min보다 크거나 같고, min+1,000,000보다 작거나 같은 자연수이다. 출력첫째 줄에 [min,max]구간에 제곱ㄴㄴ수가 몇 개인지 출력한다. 풀이)에라토스테네스의 체 방법을 사용하였고제곱수가 아닌 수를 찾는 것이 아닌, 1보다 큰 제곱수로 나누어 떨어지지 않는 수를 찾으면 되는 문제이다. 핵심은min과 max의 범위가 크므로..