소수 판별

문제

 

자연수n,m이 주어질 때, n부터m까지 존재하는 소수를 모두 출력하는 프로그램을 작성하여라. 여기서 소수란, 약수가 1과 자기자신밖에 존재하지 않는 수를 말한다.

 

입력

 

첫째 줄에 자연수 n, m이 주어진다. (1≤n,m≤20,000)

 

출력

 

첫째 줄에 n부터m까지 존재하는 소수를 모두 출력한다.

 

예제 입력

1 10

 

예제 출력

2 3 5 7

 

예제 입력

13 30

 

예제 출력

13 17 19 23 29

 

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

n과 m의 범위가 1부터 20000까지이므로 최대한 시간을 줄이기 위해 소수를 찾을 때 2부터 해당 수의 루트까지 찾는 방식으로 짜보았음. 나눠지는 수가 있으면 status 라는 정수형 변수의 값을 바꾸고 break 시키는 방식으로 진행하였음.

 

#include  <iostream>
using namespace std; 

int main() { 
	int n, m; 
	cin >> n >> m; 

	for (int i = n; i <= m; i++) { 
		int status = 0; 
		for(int j=2; j*j<=i; j++){ 
			if (i % j == 0) { 
				status = 1; 
				break; 
			} 
		} 
		if (status == 0&&i!=1) cout << i << " "; 
	} 


	return 0; 
}