...? 그걸 루트n 안에 찾는 알고리즘을 개발하면 너는 필즈상감임.
아니 필즈상이 아니라 수학 교과서에 영원히 이름이 실릴듯

루트 이야기 나오는 거 보면 전체 검증을 루트C 이내로 하란 소리가 아니라 수학공식 이용해서 하나의 수에 대해 나눠보는 문제같은데 문제 원문을 봐야겠지만 아마 이 이야기가 맞을 거임.

C가 합성수면 C = A * B (A, B는 1보다 큰 자연수). 따라서 둘 중 하나는 루트C보다 작거나 같음.
따라서 모든 수 검증할 필요 없이 루트 C이내로만 나눠봐서 검증하면 됨.

즉 내부 하나의 수에 대해 검증하는 루프는 따로 있고 그 루프를 돌리는걸 루트C번 까지 하란 문제 같은데. 즉 이중루프 구조에서 외부 루프를 루트C 만큼만.

참고로 소수 알고리즘 다룰 때 에라토스테네스의 체 이야기하면서 항상 같이 나오는 거니 검색해보면 아마 같이 나올거임.