[1016] 제곱 ㄴㄴ 수

✔ 제곱 ㄴㄴ 수

[백준 1016]

문제 분석하기

에라토스테네스의 체 알고리즘 방식으로 제곱수 판별 로직에 사용

손으로 풀어보기

1. 2의 제곱수인 4부터 max값까지 제곱수를 찾음
   • 이때 데이터를 순차적으로 탐색하는 것이 아니라 에라토스테네스의 체 방식으로 제곱수의 배수 형태로 탐색
2. 탐색한 배열에서 제곱수로 확인되지 개수를 센 후 출력

예) min = 1, max = 10

제곱수 pow	start_index	j		Check 배열
i = 2, pow = 4	1	1	1 *4 - 1 = 3 Check[3] = 4	[false, false, false, true, false, false, false, false, false, false]
		2	2 *4 - 1 = 7 Check[7] = 8	[false, false, false, true, false, false, false, true, false, false]
i = 3, pow = 9	1	1	1 *9 - 1 = 8 Check[8] = 9	[false, false, false, true, false, false, false, true, true, false]
i = 4, pow = 16	1	1	16 * 1 = 16이므로 Max인 10보다 크므로 알고리즘 종료 [false, false, false, true, false, false, false, true, true, false] count = 7

슈도코드 작성하기

Min(최솟값) Max(최댓값)
Check(Min ~ Max 사이에 제곱수 판별 배열)
for(i = 2 ~ Max 사이 반복, i * i 증가) {
    pow(제곱수)
    start_index(최솟값/제곱수)
    for(j = start_index ~ Max 사이 반복하기) {
        j * pow가 Max보다 작을 때, 최솟값, 최댓값 사이의 제곱수이므로
        Check 배열에 저장하기
    }
}
count(제곱이 아닌 수 카운트) 
for(0 ~ Max - Min) {
    Check 배열에서 제곱이 아닌 수라면 count 증가
}
count 출력하기

코드 구현하기

/**
 * 1016) 제곱_ㄴㄴ_수
 */
public class D040_1016 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // Min(최솟값)
        long Min = sc.nextLong();
        // Max(최댓값)
        long Max = sc.nextLong();
        // Check(Min ~ Max 사이에 제곱수 판별 배열)
        boolean[] Check = new boolean[(int) (Max - Min + 1)];
        // 2의 제곱수인 4부터 Max보다 작거나 같은 값까지 반복하기
        for (long i = 2; i * i <= Max; i++) {
            // pow(제곱수)
            long pow = i * i;
            // start_index(최솟값/제곱수)
            long start_index = Min / pow;
            // 나머지가 있으면 1을 더해야 Min보다 큰 제곱수에서 시작됨
            if (Min % pow != 0)
                start_index++;
            // j * pow가 Max보다 작을 때
            for (long j = start_index; pow * j <= Max; j++) {
                // 최솟값, 최댓값 사이의 제곱수이므로 Check 배열에 저장하기
                Check[(int) ((j * pow) - Min)] = true;
            }
        }
        // count(제곱이 아닌 수 카운트)
        int count = 0;
        for (int i = 0; i <= Max - Min; i++) {
            // Check 배열에서 제곱이 아닌 수라면 count 증가
            if (!Check[i]) {
                count++;
            }
        }
        // count 출력하기
        System.out.println(count);
    }
}