시간복잡도라는 개념을 먼저 공부하고 문제를 풀어보시기 바랍니다.

그것과 별개로 이 문제는 에라토스체네스의 체를 활용해야 합니다.

"시간 줄이는 것과 관련해 잘 몰라서 그런 것도 있지만" 때문에 마음에 걸려서 좀 자세하게 적습니다...ㅎ

작성하신 코드를 보면, 2중 포문으로 짜여있죠? 

문제 조건의 끝 값을 보고 만약 M=1, N=백만 이면, 바깥 for문은 약 백만 번 돌 것이고 안쪽 for문도 i에 따라 최소 한 번 부터 최대 백만 번 돌겠죠? 

따라서 해당 코드 대강의 시간 복잡도 O(N^2)이므로 최악의 경우 O(1000000000000)입니다.

그리고, 보통 O(1억)=1초 라고 보는 것으로 알고 있는데, 위에 저 큰 숫자는 1억 x 10,000이네요....?

따라서 당연하게도 해당 코드는 주어진 2초에 통과하지 못하여 시간초과인 것입니다.

해당 문제를 풀기 위하여 O(root(N))방법과 특히 윗 분께서 말씀하신 에라토스체네스의 체를 공부를 해 보시는 것을 추천드립니다!