<문제 소개>
<소스 코드>
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <unordered_map>
#include <set>
#include <cmath>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;
enum State
{
Null, NotPrime, Prime
};
bool PrimeNumberCheck(int n, map<int, State>& primeNumbers)
{
if (primeNumbers[n] == Null)
{
// n값에 처음 접근한 경우
for (int i = 2; i <= sqrt(n); i++)
{
// 나누어 떨어지는 경우가 있음 -> 소수가 아님
if (n % i == 0)
{
primeNumbers[n] = NotPrime;
return false;
}
}
// 어떤 수로도 나누어 떨어지지 않는 경우 -> 소수임
primeNumbers[n] = Prime;
return true;
}
if (primeNumbers[n] == NotPrime)
{
// n이 이미 소수가 아님이 판정난 경우
return false;
}
if (primeNumbers[n] == Prime)
{
// n이 이미 소수라고 판정난 경우
return true;
}
}
int main()
{
// 쓰레드 환경이 아닐때 버퍼를 분리하여 처리속도를 빠르게 해줌
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
map<int, State> primeNumbers;
vector<int> outputNumbers;
while (true)
{
int n;
cin >> n;
if (n == 0) break;
if (n == 1)
{
outputNumbers.push_back(1);
continue;
}
int count = 0; // 소수의 갯수
for (int i = n + 1; i <= 2 * n; i++)
{
if (PrimeNumberCheck(i, primeNumbers)) count++;
}
outputNumbers.push_back(count);
}
for (int i = 0; i < outputNumbers.size(); i++)
{
cout << outputNumbers[i] << "\n";
}
return 0;
}<풀이과정>
1. key값으로 int형, value값으로 State형을 갖는 map형으로 해당 수가 소수인지를 판별하는 컨테이너를 선언한다.
2. 결과값들을 담을 int형 벡터 outputNumbers를 선언한다.
3. while 반복문을 돌면서 n을 입력받고 0이 입력되면 반복문을 빠져나가도록 한다.
4. 1은 소수가 아니고, 모든 수는 1로 나누어 떨어지기 때문에 1은 예외사항으로 두고, n이 1일때 1보다 크고 1*2인 2보다 작거나 같은 소수들의 갯수는 2 뿐이므로 n으로 1을 입력받았다면 1일때의 소수의 갯수 1을 outputNumbers에 추가해주고 continue를 통해 다음 반복으로 넘어가준다.
5. 0이나 1이 아닌 경우에는 아래과정을 진행한다.
6. 소수의 갯수를 담을 int형 변수 count를 0으로 초기화하여 선언한다.
7. 반복자 i를 n+1부터 2*n까지 반복하며 PrimeNumberCheck() 함수를 이용해 현재 i가 소수인지 판별하고, 만약 소수라면 count를 1씩 증가시켜준다.
8. 모든 반복이 끝났다면 n보다 크고 2*n보다 작거나 같은 소수의 갯수 파악이 끝난 것이므로 count의 갯수를 outputNumbers에 추가해준다.
9. 위의 과정을 n에 0이 입력될때까지 반복하고 0이 입력되었다면 빠져나와서 outputNumbers의 모든 원소들을 출력해준다.
- PrimeNumberCheck(int n, map<int, State>& primeNumbers) 함수
1. 인자로 소수인지 확인할 값 n과 확인했던 값들을 담고있는 primeNumbers를 받아온다.
2. State는 enum으로 직접 만들어 선언한 열거형 변수로, Null이면 n값을 처음 확인하는 경우를 뜻하고, NotPrime이면 이미 n값이 소수가 아님이 확인된 경우, Prime이면 n값이 소수가 맞음이 확인된 경우를 뜻한다.
3. primeNumbers[n]의 State에 따라 함수가 동작한다.
3-1. Null인 경우
3-1-1. 2부터 n의 제곱근까지 반복하면서 반복자 i로 n을 나누었을때 나누어 떨어지는지 확인한다.
3-1-2. 만약 나누어 떨어지는 경우가 있다면 소수가 아닌 것이므로 primeNumbers[n]의 값을 NotPrime으로 변경해준 뒤, false를 리턴해준다.
3-1-3. 모든 경우에 대해 나누어 떨어지지 않는다면 소수인 경우이므로, primeNumbers[n]의 값을 Prime으로 변경해준 뒤, true를 리턴해준다.
3-2. NotPrime인 경우 -> 이미 소수가 아니므로 false를 리턴한다.
3-3. Prime인 경우 -> 이미 소수이므로 true를 리턴한다.
<코멘트>
처음에는 n을 입력받을때마다 각 범위의 모든 수에 대해 소수인지를 그때그때 확인하고 갯수를 체크해서 풀었는데 중복되는 수 때문이지 시간초과가 나왔다. 그래서 중복되는 수들, 즉 한 번이라도 소수인지 판별한 수들은 해당 결과를 저장해 놓고 그 결과들을 가져와 판단하여 시간을 줄였다! 메모리 초과가 나올 줄 알았는데 범위 제한 때문인지 나오지 않았다!
그리고 map의 특성상 처음 입력되는 값이 알아서 추가되어 기본값으로 초기화되기 때문에 처음 입력되는 수들을 어떻게 구별해야하지 생각하다가 enum을 이용해 속성을 나누어서 해결하였다!
<제출결과>
