백준 1016 <제곱 ㄴㄴ 수> C++

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

---

제곱수의 배수가 아닌 수를 찾는 문제입니다. 다만 제한이 상당히 빡빡해 시간을 최대한 단축해야 통과할 수 있습니다.

특정 범위의 수들을 제곱수로 체를 칠텐데, 우리는 어떠한 범위에서 A 의 배수들을 제거하면 NxA 의 배수들도 모두 없어짐을 알고 있습니다. NxA 의 배수들은 A 의 배수이기도 하기 때문입니다.

즉 A^2 으로 체를 친다는 말은 (N*A)^2 은 생각하지 않아도 된다는 말과 같습니다. 어차피 A^2 을 고려하며 모두 제거되었기 때문입니다. 즉 고려해야하는 수 A는 어떤 수의 배수가 아닌 수, 즉 소수임을 알 수 있습니다. 그렇기에 문제를 해결하는 프로세스는 다음과 같습니다.

 

1. 최댓값 MAX 의 제곱근 이하의 소수를 모두 구한다. ( MAX 이하의 소수의 제곱수를 모두 구하기 위해 )

2. 1 에서 구해진 소수들을 제곱한다.

3. 2 에서 구해진 소수의 제곱수들로 특정 범위를 체친다. ( 배수가 아닌 수를 찾는다 )

---

#include <iostream>

#include <array>

#include <vector>

#include <algorithm>

#include <cmath>

using namespace std;

// 소수를 찾는 함수

vector<long long int> search_unique(long long int& max) {

    // 소수 목록

    vector<long long int> uniques;

    // 수 체크를 위한 벡터

    vector<bool> nums(max, true);

    // 순회

    for (long long int i = 2; i <= max; i++) {

        // i 가 체크되어 있지 않으면

        // k 가 소수이면 nk 는 소수가 아님이 자명하므로

        if (nums[i - 1]) {

            uniques.push_back(i);

            for (long long int j = i; j <= max; j += i) {

                // j 가 체크되어 있지 않으면

                if (nums[j - 1]) nums[j - 1] = false;

            }

        }

    }

    return uniques;

}

// 벡터의 제곱수들을 구하는 함수

vector<long long int> squares(vector<long long int>& vec) {

    // 순회하며 제곱

    for (long long int i = 0; i < vec.size(); i++) {

        vec[i] = pow(vec[i], 2);

    }

    return vec;

}

// MAX 이하의 소수의 제곱수를 찾는 함수

vector<long long int> search_under_square(long long int& max) {

    // 소수의 제곱수

    vector<long long int> square_uniques;

    // max 의 제곱근 (long long int)

    long long int sqrt_max = static_cast<long long int>(sqrt(max));

    // max 이하의 소수

    vector<long long int> uniques = search_unique(sqrt_max);

    // 소수의 제곱 벡터

    return squares(uniques);

}

// 특정 수들 체로 특정 범위의 수들을 걸러내는 함수

long long int filter_nums(vector<long long int>& vec, long long int& MIN, long long int& MAX) {

    // 걸러낼 범위의 수들

    vector<bool> nums(MAX - MIN + 1, true);

    // 걸러내기

    for (auto num : vec) {

        // min 보다 큰 최소 배수

        long long int min_num = MIN%num == 0 ? MIN : num * (MIN / num) + num;

        // max 보다 작은 최대 배수

        long long int max_num = MAX%num == 0 ? MAX : num * (MAX / num);

        // 배수 체크

        for (long long int i = min_num; i <= max_num; i += num) nums[i - MIN] = false;

    }

    return count(nums.begin(), nums.end(), true);

}

int main(void) {

    // 입력

    long long int MIN, MAX;

    cin >> MIN >> MAX;

    // MAX 이하의 (소수의 제곱수)들

    auto square_uniques = search_under_square(MAX);

    // 걸러내기

    cout << filter_nums(square_uniques, MIN, MAX);

}