[백준] 제곱 ㄴㄴ 수 - 복습

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

에라스토테네스의 체

제곱수의 배수들을 제외시켜둔다

#include <iostream>
#include <vector>

using namespace std;

int check[1000001];
vector<long long int> squareNumber;

int main()
{


    long long int min, max;
    cin >> min >> max;

    for (long long int i = 2; i*i <= max; i++)
    {
        squareNumber.push_back(i*i);
    }

    long long int ret = 0;
    for (long long int i = 0; i < squareNumber.size(); i++)
    {
        for (long long int j = (min / squareNumber[i])*squareNumber[i]; j <= max; j += squareNumber[i])
        {
            if (j - min < 0)continue;
            if (check[j - min] == 0) {
                check[j - min] = 1;
                ret++;
            }
        }
    }

    cout << max - min + 1 - ret << endl;
}