[BaekJoon] 1016번 - 제곱 ㄴㄴ 수 [Java][C++]

문제 링크

---

1. 문제 풀이

min과 max 사이의 수 중에서 어떠한 제곱수로도 나누어 떨어지지 않는 수의 개수를 구하는 문제로 구간의 크기가 최대 $1,000,000$ 이고 각 수가 매우 크다. 에라토스테네스의 체처럼 미리 체크용 배열을 만들고 제곱 ㄴㄴ 수이면 체크하는 방식으로 필터링을 하면 해결할 수 있다. 이때 min이 매우 큰 수가 될 수 있어서 효율적으로 체크를 해야하는데 min이 해당 제곱수로 나누어 떨어지면 min부터 체크하면 되며, 나누어 떨어지지 않으면 몫을 하나 늘린 후 해당 수부터 체크하면 된다.

---

2. 코드

1. 풀이 [Java]

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        long min = Long.parseLong(st.nextToken());
        long max = Long.parseLong(st.nextToken());

        boolean[] check = new boolean[(int) (max - min + 1)];
        Arrays.fill(check, true);

        for (long i = 2; i * i <= max; i++) {
            long pow = i * i;
            long q = min % pow == 0 ? min / pow : min / pow + 1;

            for (long j = pow * q; j <= max; j += pow) {
                check[(int) (j - min)] = false;
            }
        }

        int cnt = 0;
        for (boolean flag : check) {
            if (flag) cnt++;
        }

        System.out.println(cnt);
    }
}

2. 풀이 [C++]

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long mn, mx;
    cin >> mn >> mx;

    vector<char> check((int)(mx - mn + 1), true);

    for (long long i = 2; i * i <= mx; i++) {
        long long pow = i * i;
        long long q = mn % pow == 0 ? mn / pow : mn / pow + 1;

        for (long long j = pow * q; j <= mx; j += pow) {
            check[(int)(j - mn)] = false;
        }
    }

    cout << count(check.begin(), check.end(), true);
}

---