[BOJ_C++] 1016번 : 제곱 ㄴㄴ 수

# 문제

# 풀이

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cstring>
#include <stack>
#include <vector>
#include <cmath>

using namespace std;

bool num[1000001]; 

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    memset(num, false, sizeof(num));
    long long min, max;
    int cnt = 0;

    cin >> min >> max;
    for (long long i = 2; i <= sqrt(max); i++) {
        long long n = min / (i * i);
        if (min % (i * i)) n++;
        while (n * i * i <= max) {
            num[n * i * i - min] = true;
            n++;
        }
    }

    for (int i = 0; i <= max - min; i++)
        if (num[i] == false) cnt++;

    cout << cnt;

    return 0;
}

• 에라토스테네스의 체의 원리를 응용하여 문제를 해결하였다.
• 먼저 max와 min 사이에 있는 최대의 수가 1000000이므로 이 결과를 저장할 bool 배열을 1000001 크기로 만들고 모두 false로 초기화 해 주었다.
• max보다 작은 제곱근들에 대해 배수를 늘려가며 해당 범위에 들어가는지 체크하고 들어가면 true로 값을 바꿔준다.
• 이때 n*i*i는 min보다 크거나 같은 i의 제곱수의 배수이다.

# 결과