이 문제는 제한 시간이 0.5s 이므로 O(Nlog(logN))으로 풀어야 한다. 따라서 에라토네스의 체를 사용해야한다. 문제를 풀면서 의문이 들었다. 바로 rst 함수 안의 for문에 i를 i--로 하면 시간 초과가 나고, i를 i++로 하면 시간 초과가 말생하지 않는다는 것이다. 이 문제는 아직 이유를 모르겠다. #include using namespace std; int prime[1000000]; int pn = 0; bool check[1000001] = { false }; int p() { check[0] = check[1] = true; for (int i = 2; i