boj 1456번 문제를 통해 보는 i<=b/p( i*p<=b 대신) 과 i>=a/p(i*p>=a 대신) 의 차이점.

i의 범위를 잡을때 long long 범위를 벗어나지 않기 위해서 i<=b/p로 작성하는 부분을 보고, 

i*p>=a도 그러한 형태로 작성할 수있지 않을까 싶어서 그렇게 수정하고 제출했을때 통과가 안되는걸 보고 어떠한 차이점이 있길래 이건 안되고 저건 되는가에 대해서 스스로 생각해보고, 그 이유에 대해서 적어보았다. 

#include <bits/stdc++.h>
using namespace std;

vector<int> sieve(int n){
    vector<int> primes;
    vector<bool> state(n+1,true);
    state[1]=false;
    for(int i=2; i*i<=n; i++){
        if(!state[i]) continue;
        for(int j=i*i;j<=n; j+=i)
          state[j]=false;
    }
    for(int i=2; i<=n; i++){
        if(state[i]) primes.push_back(i);
    }
    return primes;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    vector<int> primes=sieve(10000000);
    long long a, b;
    cin>>a>>b;
    int cnt=0;
    for(int p:primes){
        for(long long i = p; i<=b/p; i*=p)
          cnt+=(i*p>=a); //이 부분을 cnt+=(i>=a/p); 로 작성하면 틀린다. 왜인가
          /*
          i*p<=b를 i<=b/p로 작성하는 것이나, i*p>=a를 i>=a/p로 작성하는것이나 똑같아 보일 수 있다. 
          그러나 막상 엄밀하게 계산해보면, i<=b/p는 결국 인트값으로 잘려 날라가는 오차값을 생각해볼때, 
          잘려 나가는 오차값이 존재하더라도 작거나 같은 범위이기 때문에 결국 정수로 정의된 i 값에서 
          선택될 수 있는 i값이 달라지는 부분이 없다. 
          그런데 i>=a/p는 범위를 더 작은 범위까지 늘려버리기 때문에 오차가 발생한다
          예를들어 i>=1.25 형태라고 할때, 이건 i가 정수이기 때문에 가능한 경우는 i=2,3,4, 형태라고 
          볼 수 있는데, 이때에 c++에서 int 혹은 long long 의 정수 형태로 타입을 선언한뒤 
          5/4 형태로 계산하면 이건 1이 되어버려서 이때에 i가 
          가능한 값은 i=1,2,3,4,... 형태로 1이 의도와는 다르게 가능한 영역이 되어버린다. 
          그래서 이 경우에는 만약 위의 경우에 p가 저 사이 간극에 하나라도 가능한게 있다면 틀려버리게 
          되는 것이다. 
          그래서 이 경우 등호의 방향이 i<=b/p이니까 가능한 방식의 연산이고, 
          i*p>=a 형태는 그런식으로 해서는 잘못된 i가 포함 가능하게 되어버리는 것이다. 
          */
    }
    cout<<cnt;
}