[백준] 1016번 제곱 ㄴㄴ수

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의 범위가 크므로, 배열을 1부터 max값까지의 범위만큼 할당해주는 것이 아닌

min~max 범위 크기만큼만 할당해주는 것이다.

bool arr[100001]; // 즉, min과 max의 범위를 0부터 max-min값으로 대치시켜서 생각 

   max는 min + 1,000,000보다 작거나 같음

주의

변수들을 int형으로 선언하면 안된다.

제곱수 * 2 , 3,  4, ... 값들은 int형 범위를 벗어날 수 있기 때문이다.

코드)

#include <stdio.h>
using namespace std;
 
bool arr[1000001];//min -> 0, max -> max-min로 봄. min과 max의 범위를 0부터 max-min값으로 대치시켜서 생각
 
int main() {
    long long min, max, answer=0;
    scanf("%lld %lld", &min, &max);
 
    for (long long i = 0; i < max - min + 1; i++) arr[i] = false;
 
    for (long long i = 2; i*i <= max; i++) {
        if (arr[i]) continue;//이미 지워진 수라면 pass
 
        long long j = min / (i*i); // 범위 내 제곱수로 나누어 떨어지는 최소값
        if (min % (i*i) != 0) j++;
 
        for (j; i*i*j <= max; j++) {
            arr[i*i*j-min] = true; //제곱수로 나누어떨어진다면 true로 표시
        }
    }
 
    for (long long i = 0; i < max - min + 1; i++) {
        if (!arr[i]) answer++;
    }
    printf("%lld", answer);
 
    return 0;
}