백준 4948 c++ 풀이

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

 

이 문제는 bool array를 이용하여 에라토스테네스의 체를 구현해주시면 어려움이 없습니다. 하단 코드를 참고하세요.

#include <bits/stdc++.h>
#include <vector>


using namespace std;

vector<int> v;
bool era[246914];

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	for(int k = 0; k<246914; k++){
		era[k] = true;
	}
	
	era[1] = false;
	int v_size = 0;
	while(1){
		int x;
		cin>>x;
		if(x==0) break;
		v.push_back(x);
		v_size++;
	}
	for(int i = 2; i<=sqrt(246912); i++){
		if(era[i] == true){
			for(int j = 2*i; j<=246914; j+=i){
				era[j] = false;
			}
		}
	}	
	for(int i = 0; i<v_size; i++){
		int count = 0;
		for(int j  = v.at(i)+1; j<=v.at(i)*2; j++){
			if(era[j]){
				count++;
			}
		}
		cout<<count<<endl;
	}

}