문제

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

입력

• 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

출력

• 한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

---

1. 처음 소스코드 및 실수

• 당연히 '무지성'으로 소수를 구하는 방법 (2부터 N-1까지로 해당 수를 나누는 작업)은 시간초과가 날 것이 분명했기 때문에 다른 방법을 썼다.
• 각 인덱스에 해당하는 자연수가 소수이면 1, 아니면 0으로 체킹하는 벡터를 만들었다.
• 벡터를 전부 1로(소수로) 초기화시키고, 반복문을 돌면서 소수를 만날 때마다 N까지의 해당 소수의 배수들을 전부 0으로 바꿔주었다.
• 자세한 것은 아래 소스코드 참고 / 하지만 시간초과로 틀렸다.

#include <iostream> #include <vector> using namespace std; int MAX = 1000000; int main() { int M, N; cin >> M >> N; //oneForPrimes: 소수인 인덱스에는 1을 저장 //N+1칸을 할당해야 마지막 인덱스가 N //일단 모두 소수라고 해놓음. vector<int> oneForPrimes(MAX + 1, 1); oneForPrimes[0] = 0; oneForPrimes[1] = 0; //소수만 남기기 for (int i = 2; i <= N; i++) { if (oneForPrimes[i] == 0) continue; //1이 저장된 칸이 나오면 그 인덱스의 배수들의 칸을 모두 0으로 바꿔준다. else { for (int j = 2; i * j <= N; j++) { if (oneForPrimes[i * j] == 0) continue; else oneForPrimes[i * j] = 0; } } } //정답 출력 for (int i = M; i <= N; i++) { if (oneForPrimes[i] == 1) { cout << i << endl; } } }

2. 최종 소스코드 및 해결방법

• 시간을 조금 더 줄이기 위해 조금 더 향상된 에라토스테네스의 체 방식을 사용했다.

• 일단, N까지의 자연수 중, N/2 이상인 자연수들은 1을 제외하고 어떤 자연수를 곱해도 N이 될 수 없기 때문에, (즉, N의 약수가 될 수 없기 때문에), 배열에서 소수체킹하는 것은 N/2 이하의 자연수들까지만 그 배수들을 소수목록에서 지워주면 된다.
  (현재 소스코드에서는 2부터 N까지 다 체킹하고 있음)

• 더 나아가서, N까지의 자연수 중, N의 제곱근 이하의 자연수들까지만 그들의 배수를 체킹해주면 된다.
  예를 들어, 35까지의 소수들을 확인한다고 하자. 35의 제곱근은 5.xxx 이므로 5까지만 배수체킹을 해주면 되는데 이유는 다음과 같다.

• 6의 배수를 체킹하려면, $6$, $(6*2)$, $(6*3)$, $(6*4)$, $(6*5)$ 등등도 체크하기 위한 반복문을 돌아야 하는데, 이는 이미 그 전 반복문에서 체킹한 것들이다. 따라서, 6의 배수를 체킹하려면 $6*6$ 부터 체킹하는게 훨씬 효율적인데, 이미 $6*6$ 은 35를 초과하는 수이므로 6 이상의 자연수들의 배수들은 체킹할 필요가 없다는 것이다.
  이와 같은 이유로, 우리는 N까지의 소수들을 구하고 싶다면, 2부터 N의 제곱근 이하의 자연수들까지만 각각의 배수들을 배열에서 체킹하면 된다는 것이다.

• 또한, C++의 cin, cout을 사용했을 때는 위의 에라토스테네스의 체를 사용해도 시간 초과가 떴는데, C의 printf, scanf를 사용하니까 해결됐다.. 시간제한이 있는 문제라면 왠만하면 cin이나 cout은 쓰지 말자ㅠㅠ

#include <iostream> #include <vector> using namespace std; int main() { int M, N; scanf("%d %d", &M, &N); //oneForPrimes: 소수인 인덱스에는 1을 저장 //N+1칸을 할당해야 마지막 인덱스가 N //일단 모두 소수라고 해놓음. vector<bool> oneForPrimes(N + 1, true); oneForPrimes[0] = false; oneForPrimes[1] = false; //소수만 남기기 for (int i = 2; i * i <= N; i++) { if (oneForPrimes[i] == false) continue; //true가 저장된 칸이 나오면 그 인덱스의 배수들의 칸을 모두 false로 바꿔준다. else { for (int j = 2; i * j <= N; j++) { if (oneForPrimes[i * j] == false) continue; else oneForPrimes[i * j] = false; } } } //정답 출력 for (int i = M; i <= N; i++) { if (oneForPrimes[i] == true) { printf("%d\n", i); } } }