13, 14번 줄이 있으므로 9번 조건문은 필요가 없습니다. 혹은 cnt 변수도 아예 사용하지 않고 바로 13번 줄에서 check를 +1해줘도 되겠네요.
이상은 알고리즘상의 변경 없이 고칠 수 있는 부분들이었고, 시간을 획기적으로 줄이고 싶으시다면 좀더 수정이 필요합니다. 가령 테스트케이스마다 계산을 반복적으로 하는 대신 123456 ×2까지의 소수를 다 찾아두면 좋을 것입니다. 또 에라토스테네의 체를 이용하면 소수 p의 배수들을 O(n)이 아닌 O(n/p)에 할 수 있어 시간이 많이 줄어듭니다.
centa 3년 전
제가 프로그램을 잘 못짜서 그런거같습니다.
어떤식으로 생각하고 바꾸어나가야 효율적인 프로그램을 짤 수 있는지
제가 짠 프로그램을 바탕으로 부족한점과 개선할점이 알고 싶습니다.