알고리즘 문제풀이 - 소수 판별2

문제

자연수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의 대소비교를 먼저 수행해야 한다
• 에라토스테네스의 체 개념을 적용
  
  

---

#include <stdio.h>
#include <iostream>
#include <cmath>

using namespace std;

int N, M;

int numArray[20010] = { 0, };

int main() {

	scanf("%d %d", &N, &M);

	int large, small;

	if (N >= M) {
		large = N;
		small = M;
	}
	else {
		large = M;
		small = N;
	}


	// 숫자 배열 채우기
	for (int i = 1; i <= large; i++)
		numArray[i] = i;

	// large 까지의 소수를 모두 구한다 -> 소수는 자신의 값 할당,  소수가 아니면 0값을 할당!!  // 자연수 1은 소수 아니다
	for (int i = 2; i <= sqrt(large); i++) {  // 반복 횟수는 구하려는 범위 값의 제곱근 -> 모든 가능한 배수들을 판단하므로 제곱근이하 까지만 반복하여
												// 소수가 아닌 수를 모두 찾을 수 있다!!
	
		if (numArray[i] != 0) {
		
			int count = 2;
			int mul = numArray[i] * count;

			while (mul <= large) {
				numArray[mul] = 0;  // 소수가 아닌 수에 0 할당

				count++;
				mul = numArray[i] * count;
			}
		}
	}


	for (int j = small; j <= large; j++) {
		
		if (numArray[j] != 0 && numArray[j] != 1)
			printf("%d ", numArray[j]);
	}

	return 0;
}