4948.베르트랑 공준

이번에 풀어볼 문제는 백준의 베르트랑 공준이다. 이 문제는 소수만 구할 수 있으면 풀 수 있는 간단한 문제이다.

4948번: 베르트랑 공준

 

 

< Code 설명 >

#include <iostream>
#include <vector>
#define MAX 123456*2+1 //check할 최대 배열

using namespace std;

bool check[MAX]; // 소수 판별 배열(true = 소수x, false = 소수)

void sosu(){     // 미리 소수를 판별해서 둔다.
	for (int i = 2; i < MAX; i++){
		if (check[i] == true) // 이미 판별되어있다면
			continue;         // PASS
            
		for (int j = i + i; j < MAX; j += i){  // j의 배수들을 체크함
			check[j] = true; // 1과 자기자신만이 아니니까 소수아님으로 체크
		}
	}
}
int main() {
	int n;
	sosu();        // 소수판별 함수
	vector<int>v;  // 갯수를 저장할 백터, 사실 필요없다.. 그냥 출력해도됨
	int count = 0; // 소수의 갯수 저장될 변수
	while (cin >> n && n!=0){      // 0이 나오기 전까지 계속 입력받음
		for (int i = n+1; i <= 2*n; i++){
			if (check[i] == false) // false라는 것은 소수라는 의미이므로 
				count++;           // count값 상승
		} 
		v.push_back(count);        // count값 vector에 저장
		count = 0;                 // 또 확인해야하므로 0으로 초기화
	}
    
	for (int i = 0; i < v.size(); i++) // vector의 count내용 출력
		cout << v[i] << "\n";      //굳이 모아서 출력안해도 됨 그냥해봄
        
	return 0;
}

반드시 알아야할 TIP!!

포스팅하는 이유는 소수를 구하는 방법에 대해서 숙지해야할 것 같아서이다.

많은 사람들이 그랬듯 나역시 아라토스테네스의 체를 이용했다.

해당 알고리즘의 원리는 2부터 시작해서 자신들의 배수들을 모두 체크해주고 나중에 체크 안된 녀석들이 소수라는 개념이다.