[BaekJoon/C] No.1016 : 제곱 ㄴㄴ 수

https://www.acmicpc.net/problem/1016

 

 

No. 1016 문제

 

문제해석

 

어떤 정수 X가 제곱수로 나누어 떨어지지 않았을 때, 이를 제곱 ㄴㄴ수라 한다. => 예를 들면 30은 2^2, 3^2, 4^2, 5^2로 나누었을 때 모두 나누어 떨어지지 않으므로 제곱 ㄴㄴ수라고 합니다. 반대로 12는 2의 제곱인 4로 나누었을 때 나누어 떨어지므로 제곱 ㄴㄴ수가 아닙니다. 

 

소스코드 & 문제풀이

 

#include <stdio.h>
#include <math.h> //sqrt를 사용하기 위한 라이브러리

int arr[1000001];
int main() {
    long long min, max; // 큰 수를 사용할 것이므로 long long 타입을 사용합니다
    scanf("%lld %lld", &min, &max); 
    int sq = (int)sqrt(max) // max값을 제곱근 값으로 계산 후 정수로 변환합니다
    int cnt = 0; // 나누어 떨어지는 수의 개수를 카운하는 변수를 선언하고 초기화 시켜줍니다
    
    // 2부터 시작하여 max의 제곱근까지 반복합니다
    for (long i = 2; i <= sq; i++) {
        long pow = i * i; // 현재 숫자의 제곱수를 계산합니다
        
        // j를 통해 min과 가장 가까운 제곱수의 배수부터 시작해 max까지 증가하며 반복합니다
        for (long j = ((min - 1) / pow + 1) * pow; j <= max; j += pow) 
            arr[j - min]++; // j가 제곱수로 나누어 떨어지면 해당 인덱스에 체크하고 배열에 저장합니다
    }
    
    // min과 max 범위 내에서 제곱수로 나누어 떨어지는 수가 체크된 경우, cnt를 1 증가시킵니다
    for (int i = 0; i < (max - min + 1); i++)
        arr[i] && cnt++;
    printf("%d\n", max - min - cnt + 1); // cnt 를 제외한 값이 제곱 ㄴㄴ 수의 개수입니다
}

 

 

예제 입출력 결과