BAEKJOON 1016 - 제곱 ㄴㄴ 수

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

시간 복잡도를 줄이기위해 에라토스테네스의 체 방법을 사용해야했고, 공간 복잡도를 줄이기 위해 bit mask 방법과 주어진 최소값부터 에라토스테네스의 체를 적용하는 방법을 사용해 풀었습니다.

my solving

c++

#include <fstream>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
 
const ll MAX_N = 1000003;
unsigned char sieve[(MAX_N + 7) / 8];
 
ll minNum, maxNum;
 
bool isSquareNNNumber(ll number) 
{
    number -= minNum;
    return sieve[number >> 3] & (1 << (number & 7));
}
 
void removeFromSieve(ll number)
{
    number -= minNum;
    sieve[number >> 3] &= ~(1 << (number & 7));
}
 
void eratosthenes() 
{
    memset(sieve, 255, sizeof(sieve));
 
    ll maxNumSqrt = ll(sqrt(maxNum));
    ll num = 1;
    while (true)
    {
        num++;
        if (num > maxNumSqrt)
            break;
        ll i = num * num;
        
        for (ll j = minNum % i == 0 ? minNum : (ll)(minNum / i) * i + i; j <= maxNum; j += i)
        {
            if (j >= minNum)
                removeFromSieve(j);
        }
    }
}
 
int main()
{
    cin >> minNum >> maxNum;
    eratosthenes();
 
    int ret = 0;
    for (ll i = minNum; i <= maxNum; i++)
    {
        if (isSquareNNNumber(i))
            ret++;
    }
 
    cout << ret << endl;
    return 0;
}