[백준 1929] 소수 구하기

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

1929번: 소수 구하기

#include <stdio.h>
void is_prime(int m, int n)
{
	int flag;
	for (int i = m; i <= n; i++) {
		flag = 0;
		if (i == 1) continue;
		for (int j = 2; ; j++) {
			if (j * j  > i) break;
			if (!(i % j)) {
				flag = 1;
				break;
			}
		}
		if (flag == 0) printf("%d\n", i);
	}
}

int main(void)
{
	int m, n; //m <= n
	scanf("%d %d", &m, &n);
	is_prime(m, n);
	return 0;

}

소수 구하는 쉬운 문제인데, 타임아웃을 생각해야 한다. 

정수 i의 약수를 구하기 위해 for문 돌릴 때는 사실 루트 i까지만 생각해 주면 되고, sqrt 라이브러리 써주면 된다. 

그런데 만약 기본 라이브러리만 사용 가능한 경우에는, if (j * j  > i) break; 조건을 두어서 j가 i의 제곱근일 때 루프를 빠져나오도록 할 수 있다. (이때 등호 들어가면 안됨. 제곱수의 경우 j * j == i 이기 때문)

그리고 1은 소수가 아니므로 if (i == 1) continue;로 재껴준다.