[백준 4948번 / C++] 베르트랑 공준

대표적인 소수 2, 3, 5, 7 이 있는데  각 소수의 배수는 모두 소수가 아니다. 

 

예를 들어,

소수 2의 배수는 4 6 8 ..... 22222222가 있는데 모두 2로 나누어 떨어지니까 소수가 아니다 

소수 3의 배수는 6 9 12 ....33333333이 있는데 모두 3으로 나누어 떨어지니가 소수가 아니다. 

 

즉, 소수를 만나면 해당 소수의 배수를 모두 소수가 아니라고 체크를 해준다. check = true; 

 

#접근방법 

1. 소수인지 아닌지 판별하는 check라는 배열을 123456*2 만큼 생성한다. 

2. 2부터 1234567까지 반복문을 돌리면서 소수를 만나면 해당 소수의 배수들을 check에 true로 설정  

3. 이후 입력값 n을 받았을 때 n+1 부터 2*n 까지 check 배열에 false로 되어있는것만 카운팅

#include <queue>
#include <iostream>
#include <algorithm>
using namespace std; 
bool check[123456 * 2+1]; 
int main() {
	for (int i = 2; i <= 123456; i++) {
		if (check[i])continue; 
		else {
			for (int j = i*2; j <= 123456 * 2; j+=i) {
				check[j] = true; 
			}
		}

	}
	while (1) {
		int n; cin >> n;
		if (!n)break; 
		int result = 0; 
		for (int i = n + 1; i <= 2 * n; i++) {
			if (!check[i])result++; 
		}
		cout << result; 
		cout << endl; 
	}
}

 

4948번: 베르트랑 공준