[백준 - 1016] 제곱 ㄴㄴ 수

min부터 max 사이에서 어떤 제곱수로도 나누어떨어지지 않는 수의 개수를 구하는 문제다. 범위의 시작값이 매우 클 수 있으므로, 처음부터 max까지 체를 만들면 낭비가 크다.

그래서 길이가 max - min + 1인 배열만 만들고, 각 제곱수의 배수가 되는 위치만 표시했다. 예를 들어 제곱수 p²에 대해 구간에서 처음 만나는 배수는 아래처럼 구한다.

start = ceil(min / p²) * p²

그 뒤 start, start + p², ...를 표시하면 된다. 이미 표시된 수는 다시 빼지 않도록 체크 배열을 같이 사용했다.

핵심은 큰 수 전체가 아니라, 문제에서 요구한 구간만 메모리에 둔 것이다.

문제: 1016 제곱 ㄴㄴ 수 · 코드: GitHub에서 보기