백준 9020 c++ 풀이

안녕하세요 오늘은 에라토스테네스의 체를 이용한 소수판정 문제를 풀어보겠습니다.

 

이러한 소수 판정문제는 bool array를 이용하여 에라토스테네스의 체를 구현해주시면 쉽게 풀립니다. 하단 코드를 참고하시길 바랍니다.

 

#include <bits/stdc++.h>

using namespace std;
bool era[9999];

int main(){
	for(int i = 1; i<9999; i++){
		era[i] = true;
	}
	era[1] = false;
	for(int i = 2; i<=sqrt(9999);i++){
		if(era[i]){
			for(int j = 2*i; j<9999; j+=i){
				era[j] = false;
			}
		}
	}

	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int t;
	cin>>t;
	for(int i= 0; i<t; i++){
		int n;
		cin>>n;
		int l = n/2, r= n/2;
		while(1){
			if(era[l] == true and era[r] == true){
				break;
			}
			l--; r++;
		}
		cout<<l<<" "<<r<<endl;

	}

}