문제

어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수가 몇 개 있는지 출력한다.

입력

• 첫째 줄에 두 정수 min과 max가 주어진다.

출력

• 첫째 줄에 min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수의 개수를 출력한다.

제한

• 1 ≤ min ≤ 1,000,000,000,000
• min ≤ max ≤ min + 1,000,000

---

1. 해결방법 및 소스코드

• 일단, [제한]에서 보듯이, min값이 int로 표현할 수 있는 범위를 넘어가기 때문에 min과 max를 long long 자료형으로 지정해주어야 한다.
• 배열도 max만큼의 칸을 할당해줄 수 없으므로, [제한]의 두 번째 조건을 이용해 범위내의 수의 총 개수인
  max-min+1칸을 할당해주도록 한다.
• 해당 배열은 제곱ㄴㄴ수가 맞으면 0, 아니면 1을 저장한다.
• 배열의 인덱스를 i라고 하면, 인덱스가 실제로 나타내는 수는 min + i이다.
• 이제부턴 범위 내의 각 수가 제곱ㄴㄴ수인지 확인할건데, 확인을 시작할 인덱스는 start가 정한다. 예를 들어, 범위가 21에서 35일때, 먼저 2의 제곱인 4로 나누어떨어지는 수들을 제곱ㄴㄴ수에서 지워보자.
  어느 수부터 지워야 할지 정해야 하는데, 21 / 4는 5이고, 21~35에서는 24부터가 4로 나눠떨어지는 수이므로 start는 5에서 1을 더하고 4를 곱한 다음(즉, 24를 만들고) min을 뺀 인덱스이다.
• 만약 처음부터 min 값이 20과 같이 4로 나눠떨어지는 수이면 start를 바로 0으로 주면 된다.
• 그렇게 start를 정하고 for loop으로 배열을 돌면서 $k^2$으로 나눠떨어지면 제곱ㄴㄴ수에서 제외시켜준다. 이 때, for loop을 도는 과정에서도 시간을 줄이는 방법이 있는데, 어차피 $k^2$으로 나눠떨어지는 수들을 제곱ㄴㄴ수에서 지워줄 것이므로 for loop의 마지막에서 start를 start++하지말고, $k^2$만큼씩 증가시켜주면 훨씬 빠르다.

#include <iostream> #include <vector> int main() { //min, max 입력 long long min, max; long long count = 0; scanf("%lld %lld", &min, &max); //제곱ㄴㄴ수이면 0을 저장, 아니면 1을 저장 //초기: 다 제곱ㄴㄴ수라고 가정하고, 제곱ㄴㄴ수가 아닌 수들만 1로 바꿔준다. //배열의 인덱스를 i라 하면 각각의 인덱스가 나타내는 수는 사실상 i+min 이다. int isntNoNo[max - min + 1] = { 0, }; //max보다 큰 제곱수로 범위 내의 수를 나누는 것은 소용없음. for (long long k = 2; k * k <= max; k++) { long long start; if ((min % (k * k)) == 0) { start = 0; } else { start = ((min / (k * k)) + 1) * (k * k) - min; } for (; start < max - min + 1; start += (k * k)) { //이미 제곱ㄴㄴ수가 아니라고 확정난 칸은 패스 if (isntNoNo[start]) continue; else { isntNoNo[start] = 1; } } } for (int i = 0; i < max - min + 1; i++) { if (isntNoNo[i] == 0) count++; } printf("%d ", count); }