3896 - 소수 사이 수열

에라토스테네스의 체를 써서 2~1299709 까지 소수를 모두 저장하고 입력되는 정수 k에 대해 upper_bound(k) - lower_bound(k) 를 했다.

여기서 말한 upper_bound(k) 는 k와 같거나 k보다 작지 않은 가장 작은 수를 의미하고, lower 는 그 반대이다.

C++ 라이브러리에 있는 std::upper_bound 랑 std::lower_bound 로는 원하는 위치가 나오지를 않았다. 라이브러리 함수는 수가 같은 경우엔 그 다음 iterator를 반환하고 있었다. 그래서 직접 구현했다.