백준 1016 제곱 ㄴㄴ수

 

 

에라토스테네스의 체 문제이다

 

 

만약, "min에서 max까지 순회하면서 각 값이 2~백만의 값의 제곱수로 나누어 떨어질경우 pass"

하는 식으로 알고리즘을 짜면 n^2이 되기때문에 시간초과가 난다.

 

 

따라서 백만짜리 배열을 선언하고

#

"i"는 2~max까지 순회하며 다음을 반복

##

(i*i) * j 는 제곱 YES수이므로

배열[(i*i) * j]를 true로 바꾼다.

다만 (i*i) * j의 값을 min~max 사이로 해싱한다 민다

j+=1.

##

#

마지막에 배열에서 false가 몇개인지 샌다

#

와 같은 알고리즘은 배열의 값을 중복해서 체크하는 경우가 거의 없기 때문에 

시간복잡도를 n으로 봐도 되므로(즉, 백만) 시간 안에 해결 가능하다.

 

#include <iostream>
using namespace std;
bool isSqr[1000001];
int main() {
    long long min, max;
    cin >> min >> max;
    for (long long i = 2; i * i <= max; i++) {
        long long start = min / (i * i);
        if (start * i * i != min) start++;
        for (long long j = start; i * i * j <= max; j++) {
            isSqr[i * i * j - min] = true; 		
        } 	
    } 	
    int count = 0; 	
    for (int i = 0; i < max - min + 1; i++) {
        if (!isSqr[i]) count++; 	
    } 	
    cout << count << endl;  	
    return 0; 
}