2부터 루트 n까지 찾는 방법은 85,34 같은 예외가 있는거 같아서 a%b와 b의 공약수를 찾는 방법으로 해봤는데 TLE가 나오네요...혹시 여기서 시간을 더 줄일 수 있는 방법은 없을까요?

n1과 n의 공약수는 1부터 n1까지 검사해봐도 되지만 가장 빠른 방법은 (n과 n1의 공약수) = (n1과 n%n1의 공약수)=(n%n1과 (n%n1)%(n%n1)의 공약수) = ... 위의 성질을 활용하는 것입니다. 이는 반복문으로 사용해도 되고, 재귀함수로도 만들 수 있습니다. 아니면 배열을 공부해보고 나서 에라토스테네스의 체를 응용해 보아도 좋을 것 같습니다.