[1016] 제곱ㄴㄴ수

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

분류 : 소수판별법

백준 1016 제곱ㄴㄴ수

주어진 범위에서 제곱수로 나누어 떨어지지 않는 숫자의 개수를 구하라

---

구현 포인트

1) 일반 정수의 제곱의 배수보다는 소수의 제곱을 고려하는 것이 더 경우의 수가 적어진다.
(소수의 제곱의 배수만 고려해도 모든 경우를 커버할 수 있기 때문이다.)

2) 소수의 제곱을 고려해서 배수의 갯수를 뺄 때 중복되는 것이 있음에 주의해야 한다.

(ex, 16의 9배 = 9의 16배)

3) 계산과정에서 int범위가 넘어 갈 수 있음에 유의해야 한다.

구현된 코드는 아래와 같다.

소수는 에라토스테네스의 체를 이용하였고,

중복된 수는 갯수에서 제외하기 위해 check라는 배열을 만들어서 제곱의 배수는 0으로 만들어서

최종적으로 제곱ㄴㄴ수를 check되어있는 수를 세어서 구하였다.

#include<iostream>
#include<vector>
 
using namespace std;
 
int main() {
    long long min, max;
    cin >> min >> max;
    long long len = max - min + 1;
    vector<bool> isprime(1000001, true);
    vector<int> check(len, 1);
    for (long long i = 2; i*i <= max; i++) {
        if (isprime[i]) {
            for (long long j = i*2; j*j <= max ; j+=i) {
                isprime[j] = false;
            }
            long long square = i*i;
            for (long long s = (((min-1)/square)+1)*square; s <= max; s+=square) {
                if (s >= min) check[s - min] = 0;
            }
        }
    }
    len = 0;
    for (int i: check) {
        len += i;
    }
    cout << len << endl;
}