[백준]1929_소수 구하기

https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

백준 1978, 2581과 비슷하게 소수를 구하였는데,

 

시간초과가 일어났다.

 

 

왜 시간초과가 일어났는지 보니깐,

for문으로 2부터 그 수까지 계속 확인해보는게 문제였다.

 

참고링크 ↓↓

https://www.acmicpc.net/board/view/39203

글 읽기 - ★☆★☆★ [필독] 소수 구하기 FAQ ★☆★☆★

 

 

 

설명을 해보자면

소수를 구하는 수를 18이라고 생각하면

2부터 18까지 일일이 나눠보고, 나눠떨어지는 여부를 확인 할 것이다.

 

그치만, 18의 약수를 생각해보면,

1, 2, 3, 6, 9, 18가 있다.

 

1, 2, 3, 6, 9, 18 이렇게 보면 

1 * 18 = 18

2 * 9 = 18

3 * 6 = 18 이다.

 

이 관계를 보자면,

18 / 2 = 9

18 / 3 = 6

-----------------

18 / 6 = 3

18 / 9 = 2

 

 

일정 값을 기준으로 몫과 나눈 값이 반대로 바꿔서 나누는 것을 볼 수가 있다.

 

 

따라서, 18의 제곱근인 4.2426..까지만 확인해본다면

그 나머지 연산은 나눈는 몫과 나눈 값이 반대로 바뀌게 되는 연산이기 때문에

굳이 확인 할 필요가 없다는 말이다. 

 

그래서 확인 하고자하는 수의 제곱근을 구하여

제곱근 까지 나눠 확인을 하였다.

 

소스코드 ↓

#include <stdio.h>
#include <math.h>

int main() {
	int start, end;
	int count = 0;
	int sqrt_start;
	scanf("%d %d", &start, &end);
	for (; start <= end; start++) {
		count = 0;
		sqrt_start = sqrt(start);
		for (int i = 1; i <= sqrt_start; i++) {
			if (start % i == 0) {
				count++;
				if (count > 2)
					break;
			}
		}
		if (count == 1 && start != 1) {
			printf("%d\n", start);
		}
	}
	
	return 0;
}