문제 링크입니다: https://www.acmicpc.net/problem/3896
에라토스테네스의 체를 이용하여 푸는 문제였습니다.
주의할 점은 소수 사이 수열의 길이는 (소수들의 개수 + 1)이라는 것입니다.
#include <iostream>
#include <vector>
using namespace std;
const int MAX = 1299709 + 1;
int minFactor[MAX];
void eratosthenes(void)
{
minFactor[0] = minFactor[1] = -1;
for (int i = 2; i < MAX; i++)
minFactor[i] = i;
for (int i = 2; i*i < MAX; i++)
if (minFactor[i] == i)
for (int j = i * i; j < MAX; j += i)
if (minFactor[j] == j)
minFactor[j] = i;
}
int main(void)
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int T;
cin >> T;
eratosthenes();
for (int t = 0; t < T; t++)
{
int K;
cin >> K;
if (minFactor[K] == K)
cout << 0 << "\n";
else
{
int result = 1;
int temp = K + 1;
while (1)
{
if (minFactor[temp] == temp)
break;
temp++;
result++;
}
temp = K - 1;
while (1)
{
if (minFactor[temp] == temp)
break;
temp--;
result++;
}
//중요
cout << result + 1 << "\n";
}
}
return 0;
}
개발환경:Visual Studio 2017
지적, 조언, 질문 환영입니다! 댓글 남겨주세요~
'알고리즘 > BOJ' 카테고리의 다른 글
백준 2904번 수학은 너무 쉬워 (0) | 2019.01.30 |
---|---|
백준 1456번 거의 소수 (0) | 2019.01.30 |
백준 16563번 어려운 소인수분해 (0) | 2019.01.30 |
백준 9020번 골드바흐의 추측 (0) | 2019.01.30 |
백준 2018번 수들의 합 5 (0) | 2019.01.29 |