Baekjoon 3896 소수 사이 수열

Link https://www.acmicpc.net/problem/3896

결과 4152 KB / 24 ms

언어 C++17

 

풀이

최대 값이 1299709로 충분히 배열로 만들만 하다

입력값을 기준으로 조건을 걸어서 소수라면 0을

합성수라면 1 ~ 합성수까지의 개수를 구하면 된다.

매번 결과를 구해도 될만큼 테스트 케이스가 많지 않기 때문에 매 순간 돌려도 된다.

해당 수가 소수인지 아닌지를 판별하는 방법은 에라토스테네스 체를 구하는 과정의 배열을 재 사용하도록 한다.

 

소스코드

#include <iostream>
#include <vector>

using namespace std;

const int MAX = 1299709;

bool prime[MAX + 1] = { true, true };
vector<int> primes;

void eratos() {

	for (int i = 2; i <= MAX; i++)
	{
		if (!prime[i])
		{
			primes.push_back(i);
			for (int j = i * 2; j <= MAX; j += i)
				prime[j] = true;
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
		
	int n; cin >> n;

	eratos();

	for (int i = 0; i < n; i++) {
		int input; cin >> input;

		if (!prime[input])
			cout << 0 << '\n';
		else
		{
			int pos = 0; while (primes[pos + 1] < input) pos++;

			cout << primes[pos + 1] - primes[pos] << '\n';
		}

	}


	return 0;
}