[BOJ] 제곱 ㄴㄴ 수

제곱 ㄴㄴ 수

TimeLimit	MemoryLimit	Condition	TAG
1s	128MB	(1 ≤ min ≤ 1,000,000,000,000, min ≤ max ≤ min + 1,000,000)	에라토스테네스의 체, Math

아니 이렇게 나와서 범위를 저렇게 잡았더니 10%대에서 계속 틀린다…

이유를 못 찾고서 왜 안되는 것이냐 하면서 벌에별거 다 바꿔보다가

처음 제출에서 범위만 그냥 1’000’000 하고서 냈더니 AC를 맞음.

머리에 총 맞은 것처럼 머리가 ㄹㅇ 띵했는데.. 그냥 직접 계산해서 넣지 말고 sqrt(M)로 해서 작업하도록 하자.

괜히 이상한 짓 하다가 이렇게 된다…ㅠㅜ

정답 코드

#define MAX 200000001
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cstring>
#include <queue>
#include <stack>
#include <math.h>
using ll = long long;
using namespace std;

// 707,106.7811865475
bool table[1'000'001];
bool visited[1'000'001];
ll real_max = 708'000;


ll m, M;



int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    
    cin >> m >> M;
    
    
    ll limit = (ll)sqrt((double)M);
    // 아 직접 순회 범위 자체가 작구나!>!?!
    // 새로운 깨달음
    
    ll result = 0;
    
    
    for(ll i = 2; i <= limit; i++){
        if(table[i]) continue;
        
        for(ll j = i+i; j <= limit; j+=i) table[j] = true;
        
        
        // 난 개빡돌이노? visited 만들엇으면 그냥 해버리면 되는걸 왜 안 한거야
//         cout << i << " " << (m / (i*i)) * (i*i) << "\n";
        for(ll j = ((ll)(m / (i*i))) * (i*i); j <= M; j += (i*i)){
            if(j < m || visited[j - m]) continue;
            
            visited[j - m] = true;
            result++;
        }
        
    }
    
    
    
    
    
    cout << M - result - m + 1;

}