백준 3896 - 소수 사이 수열 (C++)

 

어떤 수 K가 주어졌을 때, K를 포함하는 소수 사이 수열의 길이를 구하는 문제이다.

예를 들어, K가 6이라고 해보자.

 

K와 가장 가까운 소수는 3과 7이다.

이 때, 6을 포함한 소수 사이 수열은 가장 가까운 소수 사이의 수열이기 때문에 (4, 5, 6)이 된다.

즉, K를 포함한 소수 사이 수열의 길이는 3이 되는 것이다.

 

이번엔, K를 11이라고 가정해보자.

11은 소수이기 때문에, 소수 사이 수열에 포함되지 않는다.

고로, 0을 출력하면 된다.

 

 

문제 풀이

---

 

이러한 소수에 대한 문제가 나오면 일단은 '에라토스 테네스의 체' 라는 알고리즘을 떠올리면 된다.

물론 다른 방법으로 풀어야 하는 경우도 많지만, 에라토스 테네스의 체는 소수를 판별하는 가장 대표적인 알고리즘이기 때문에 도움이 되는 경우가 많다.

 

에라토스 테네스의 체란?

 

이런 식으로 숫자를 쭉 나열해보자.

이 때, 앞에서부터 탐색하며 배수를 모두 지워나가는 것이다.

1의 경우엔, 모든 수가 배수기 때문에 따로 판별하지 않는다.

 

이렇게 빨간색으로 칠한 것은 그 색을 지웠다는 의미이다. 1을 먼저 지우고 시작하다.

이제 2의 배부터 하나씩 지워보도록 하겠다.

 

2의 배수를 모두 지우면, 홀수만 게 된다. 여기서 다시 3의 배수를 지워보자.

 

 

이렇게, 숫자가 많이 사라진 것을 확인할 수 있다.

앞에서부터 계속 반복하며 모든 배수를 다 지워보자.

 

 

이렇게, 소수만 남는 것을 확인할 수 있다.

소수는 1을 제외한 어떤 수의 배수가 될 수 없기 때문에, 배수를 모두 지우면 소수만 남게되는 것이다.

 

이렇게, 에라토스 테네스의 체로 소수만을 판별했다면, K를 기준으로 가장 가까운 소수를 구할 수 있을 것이다.

먼저, 위의 표를 1차원 배열로 저장해보자.

 

std::vector<int> Nums(25 + 1);

 위처럼 에라토스 테네스의 체를 이용하여 인덱스가 소수인가 아닌가를 판별한 뒤, 소수가 아닌 인덱스의 값을 -1로 바꿔주게 된다면, 소수인 인덱스의 값은 0으로 되어있을 것이다.

 

즉, Nums[K]를 기준으로 K를 1씩 빼가며, 가장 가까이에 있는 값이 0인 인덱스를 구하면 그 것이 바로 앞의 소수이고

K를 1씩 더해가며, 가장 가까이에 있는 값이 0인 인덱스를 구하면 그 것이 바로 뒤의 소수인 것이다.

 

앞의 소수와 뒤의 소수를 구했다면, (뒤의 소수  -  앞의 소수) 값이 소수사이수열의 길이가 된다.

 

 

 

풀이 코드

---

	Nums.resize(1299710, 0);
	Nums[0] = -1;
	Nums[1] = -1;

 

문제에서 값의 범위는 100000번째 소수(1299709) 보다 작거나 같다고 정해두었기 때문에, 배열은 1299709 + 1로 Resize하였다.

 

void FindPrimeNumber()
{
    for (int i = 2; i * i <= 1299709; i++)
    {
        if (Nums[i] == 0)
        {
            for (int j = i * i; j <= 1299709; j += i)
            {
                Nums[j] = -1;
            }
        }
    }  
}

 

위는 에라토스 테네스의 체에 관한 코드이다.

 

먼저, 앞에서부터 1씩 탐색하며 해당 숫자가 지워졌는지는 확인한다.해당 숫자가 이미 지워져있다면, 그 배수또한 모두 이미 지워진 상태이기 떄문에 다시 검사할 필요가 없기 떄문이다.

 

만약, 현재 숫자가 지워지지 않았다면, 반복문을 돌며 그 배수를 모두 지워주면 된다.

 

int NumOfTestcase = 0;
std::cin >> NumOfTestcase;

std::vector<int> Answers(NumOfTestcase);

 

배수들을 모두 지워주었다면, 입력을 받자. 테스트 케이스의 수를 입력받은 뒤, 그 개수만큼 답을 보관할 자료구조를 resize해준다.

 

다음은 NumOfTestCase 만큼 반복문을 돌며 아래 코드를 반복해주면 된다.

int K = 0;
std::cin >> K;

if (Nums[K] == 0)
{
    Answers.push_back(0);
    continue;
}

 

먼저, K를 입력받은 뒤 K가 소수인지 아닌지 확인하자.

K가 소수라면, 소수 사이 수열이 없기 때문에 길이는 0이다.

 

int PrevPrimeNumberIndex = 0;
int NextPrimeNumberIndex = 0;

for (int i = K - 1; i >= 0; i--)
{
    if (Nums[i] == 0)
    {
        PrevPrimeNumberIndex = i;
        break;
    }
}

for (int i = K + 1; i <= 1299709; i++)
{
    if (Nums[i] == 0)
    {
        NextPrimeNumberIndex = i;
        break;
    }
}

 

다음은 반복문을 돌며, 바로 앞의 소수와 바로 뒤의 소수를 구하면 된다.

어렵지 않게 구할 수 있다.

 

Answers[Case] = (NextPrimeNumberIndex - PrevPrimeNumberIndex);

 

이후, 답을 자료구조에 넣어주면 끝이다.

 

for (int i = 0; i < NumOfTestcase; i++)
{
	std::cout << Answers[i] << "\n";
}

테스트 케이스 반복문이 모두 끝난 뒤, 위와 같이 출력해주면된다.

 

 

 

---

 

문제 자체가 어려운 문제는 아니었다.

에라토스 테네스의 체를 알고 있느냐 모르고 있느냐가 이 문제의 관건이었을 것이라 생각한다.