[백준 01016] 제곱 ㄴㄴ 수 [C]

문제

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

 

입력

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

출력

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

제한

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

---

풀이

문제에서 주어진 "제곱 ㄴㄴ 수"는 수론에서 제곱 인수가 없는 정수(Square-free Integer)로, 1이 아닌 제곱수를 인수로 지 않는 양의 정수이다.

 

쉽게 정수에 대해 소인수분해를 했을 때 동일한 글에서는 SFI라 부르겠다.

 

최대 1e+12 + 1e+6라는 큰 수가 주어지는 문제이다. 효율적으로 계산해보자.

 

소수가 아닌 수를 구할때 사용했던, 에라토스테네스의 체 원리를 이용해 이번에는 SFI가 아닌 수를 구했다.

범위(max - min)에서 제곱수(cnt)를 빼고, 1을 더한 수가 SFI 의 개수이다. 

• 입력받은 min, max 사이에 나눌 수 있는 제곱수의 범위를 구한다.

for (long i = 2; i <= sq; i++){ }

• 제곱수의 배수이면서, min이상인 수부터, max까지 존재하는 제곱수의 배수만큼 배열들의 값을 증가시킨다.

for (long i = 2; i <= sq; i++){
    long pow = i*i;
    for (long j = ((min-1)/pow +1)*pow; j <= max; j += pow)
        arr[j-min]++;
}

• 다시 배열을 탐색하며, 0이 아닌 값들을 찾을 때마다 제곱수의 개수(cnt)를 증가시켜 결과 출력에 사용한다.

다루는 수가 최대 1e+12 + 1e+6 이다 보닌깐 반복문에서 사용하는 변수의 자료형도 long형 이어야 한다는 점에 유의하자.

---

소스코드

#include <stdio.h>
#include <math.h>
int arr[1000001];
int main(){
    long long min, max;
    scanf("%lld %lld", &min, &max);
    int sq = (int)sqrt(max), cnt = 0;
    for (long i = 2; i <= sq; i++){
        long pow = i*i;
        for (long j = ((min-1)/pow +1)*pow; j <= max; j += pow)
            arr[j-min]++;
    } 
    for (int i = 0; i < (max-min +1); i++)
        arr[i] && cnt++;
    printf("%d\n", max-min-cnt +1);
}

---

출처

1016번: 제곱 ㄴㄴ 수

 

Square-free integer - Wikipedia