자연수의 크기가 크지 않다면 (10자리정도?)

완전 탐색으로 3자리씩 끊을 수 있는 모든 경우의 수를 가지고 각각에 대해 sqrt(n) 소수판별을 하면 되지 않을까요

수가 작다면..

윗 분 말씀대로 하면 될 거 같아요.

조금 개선하면 각 구간에 대해 소수 판별을 해 놓고, 완전 탐색하면 같은 구간을 여러 번 확인할 필요가 없어지니 조금 빨라질 거 같아요.