백준 1929번 문제에 대한 코드가 시간 초과가 발생했다.
시간 초과가 발생하는 코드는 아래와 같다.
소수인지 아닌지 판별하기 위해 2부터 num-1까지 루프를 돌면서 0으로 나누어 떨어지는지 아닌지 확인하는 로직이다. 루트를 돌면서 마지막까지 0으로 나누어 떨어지지 않아야 소수로 판별된다. 하지만 모든 수를 루프를 돌면서 체크하는 것은 시간 초과의 원인이 된다.
따라서 이중 for문의 범위를 아래와 같이 변경한다.
num -> int(num**0.5)+1
이와 같이 변경한 이유는 약수는 대칭으로 이루어져 있기 때문에 이러한 성질을 이용하기 위해서이다.
16을 예시로 들면서 설명하면,
16의 약수는 1, 2, 4, 8, 16이다. 즉 1X16, 2X8, 4X4로 대칭을 이룬다.
따라서 16의 제곱근(=4) 이하의 수까지만 확인해보면 동일한 결과를 얻을 수 있다.
