백준 3896 _ 소수 사이 수열

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

3896번: 소수 사이 수열

---

⭐ 내 소스 코드

#include<iostream>
#include<vector>
using namespace std;


int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	vector<int> test_case;
	int num,temp,strat,end;
	bool * vec = new bool[1299710];
	
    //범위 내 소수가 아닌 수는 모두 true로 세팅
	for (int i = 2; i < 1299710; i++) {
		for (int j = i; i*j>2 && i*j<1299710; j++) {
			vec[j*i] = true;
		}
	}


	cin >> num;
	for (int i = 0; i < num; i++) {
		cin >> temp;
		test_case.push_back(temp);
	}

	
	for (int j = 0; j < test_case.size(); j++) {
		int temp = test_case[j];
        //소수가 아닐 경우
		if (vec[temp] == true) {
			strat = temp;
			end = temp;
			//소수가 나올 때 까지 strat값을 줄여준다
			while (true) {
				if (vec[--strat]!= true) {
					break;
				}
			}
			//소수가 나올때까지 end값을 올려준다
			while (true) {
				if (vec[++end]!= true) {
					break;
				}
			}
			cout << end - strat<<'\n';
		}
        //소수일 경우
		else {
			cout << 0 << '\n';
		}
	}
	
	return 0;
}

 

🙏 문제 풀이

• 너무 큰 배열은 new를 이용해서 선언해주어야 된다
• 위의 경우 배열이 0으로 자동 초기화가 된다고 한다
• 범위 내의 소수가 아닌 수들을 에라토스테네스의 체를 이용하여 걸러낸다
• 입력받은 수가 소수가 아닐 경우, 해당 수에서 계속 감소를 시켜 가장 가까운 소수를 찾아낸다 - strat
• 마찬가지로 해당 수에서 계속 증가시켜 가장 가까운 소수를 찾아낸다 - end
• end와 strat를 뺀 값이 우리가 구하고자 하는 값
• 입력받은 수가 소수일 경우 0을 출력해준다