[백준] 1016.cpp : 제곱 ㄴㄴ 수

www.acmicpc.net/problem/1016

1016번: 제곱 ㄴㄴ 수

---

• 숫자의 범위가 1조까지 가기 때문에, 적절한 자료형을 선택한다.
• 에라토스테네스의 체를 이용해 제곱수의 배수들을 걸러준다.
• 그렇다고 1조까지의 모든 값들에 대한 배열을 만들수도 없고, 반복문을 전부 돌릴수도 없기 때문에, 최솟값과 최댓값 사이의 값들에 대해서만 검사를 해준다.
• 두 수 차이의 최댓값이 백만이기 때문에, 최솟값부터 시작해서 최댓값까지만의 배열을 만들어서 걸러준다.

---

#include <iostream>

#define ull unsigned long long 

using namespace std;

ull mini, maxi;
bool val[1000001];                                      // 에라토스테네스의 체, min 과 max 사이의 값들에 대한 배열
int number;

int main(void)
{
    cin >> mini >> maxi;

    for(ull i = 2, cur, sum ; i * i <= maxi ; i++)      // 에라토스테네스의 체로 1보다 큰 제곱수를 걸러냄
    {
        cur = i * i;                                    // cur 은 현재 반복문의 제곱값
        sum = mini - (mini % cur);                      // 거를 값, 어차피 min 과 max 사이 값들만 확인하므로 min 근처 값부터 확인한다
        while(sum <= maxi)
        {
            if(sum >= mini)
            {
                val[sum - mini] = true;                 // 제곱값의 배수라면 val 의 해당 인덱스에 표시
            }
            sum += cur;
        }
    }
    for(int i = 0 ; i <= maxi - mini ; i++)             // 전체 배열들 중 걸러지지 않은 값들의 갯수를 셈
    {                                                   // 범위는 max - min 값까지
        if(val[i] == false) number++;
    }
    cout << number << endl;
}