코후닝

알고리즘 분류: 수학, 정수론, 소수 판정, 에라토스테네스의 체 문제 링크: https://www.acmicpc.net/problem/1016 1016번: 제곱 ㄴㄴ 수 어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수 www.acmicpc.net 【 풀이 】 에라토스테네스의 체를 활용하여 해결하는 문제이다. 처음엔 2부터 하나씩 제곱해 가면서 4, 9, 16, 25, 36.. 등의 제곱수들로 나누어 떨어지는 지를 체크해서 하나씩 제거해 가는 아이디어를 떠올렸다. 하지만 가능한 min 값이 0부터 1,000,000,000,000, 즉 1조나 된다. ..