[백준] 1929번

문제출처: https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

 

소수 구하는 알고리즘 구현은 경험이 있기 때문에 코드를 금세 짰다.

두 수가 주어지는데, 그 두 수를 포함한 숫자 사이의 소수를 모두 출력하는 것이다.

for문을 돌려서 소수로 판정나면 그 수를 print해주는 방식을 이용했다.

 

문제는 시간초과가 일어난다는 점이었다.

머리를 싸매다가 다른 사람들의 제출 코드도 참고하고, 인터넷에서 검색해서 찾아봤다.

이중 반복문 내에서 1과 자신을 제외한 값으로 나누어떨어지지 않는다면 소수로 판정하는데,

숫자가 크면 그 범위가 너무 넓었다. 이것때문에 인터넷을 찾아봤더니 제곱근까지 검사해도 소수가 판정된다기에

범위를 제곱근까지로 변경해서 반복문의 범위를 확 줄였다.

그리고 하나라도 나누어떨어지는 값이 있으면 바로 break해서 반복문을 빠져나오는 형식으로 변경했다.