제곱 ㄴㄴ 수 (어렵)

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

1016번: 제곱 ㄴㄴ 수

• 1 ≤ min ≤ 1,000,000,000,000
• min ≤ max ≤ min + 1,000,000

범위가 커 보이지만 min과 max의 사이이므로 1000000이다.

 

데이터를 순서대로 탐색하는 것이 아니라

에라토스테네스의 체의 원리를 사용하면 된다.

제곱수의 배수를 없애는 방식으로!

 

그냥 생각없이 에라토스테네스를 쓰기에는

숫자가 너무 크다 check 배열이 너무 커진다.

 

index를 0부터 max - min까지로 만들자

 

#include <iostream>
#include <vector>
 
using namespace std;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    long min, max;
    cin >> min >> max;
    vector<bool> check(max - min + 1);
 
    // 2의 제곱수인 4부터 max보다 작거나 같은 값까지 반복
    for (long i = 2; i * i <= max; i++)
    {
        long pow = i * i; // 제곱수
        long start_index = min / pow;
 
        if (min % pow != 0)
        {
            // 나머지가 있으면 1을 더해주어야 min보다 큰 제곱수부터 시작
            start_index++;
        }
 
        // 제곱수의 배수들을 이제 true로 바꾸자.
        for (long j = start_index; pow * j <= max; j++)
        {
            check[(int)((j * pow) - min)] = true;
        }
 
    }
 
    int ans = 0;
 
    for (int i = 0; i <= max - min; i++)
    {
        if (!check[i])
            ans++;
    }
    cout << ans << '\n';
 
    return 0;
}