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

문제

 

 

풀이

에라토스테네스의 체를 이용해 주어진 범위 내의 소수의 개수를 구하였다.

#include <iostream>
#include <cmath>

using namespace std;

int main() {
	int a[246913];
	int n;
	
	cin >> n;

	while (1) {
		int count = 0;

	
		a[0] = 0;
		a[1] = 0;

		for (int i = 2; i <= 2 * n; i++)
			a[i] = 1;

		for (int i = 2; i <= int(sqrt(2 * n)); i++) {
			for (int j =2; i*j <= 2*n; j++) {
				a[i*j] = 0;                  
			}
		}

		for (int k = n+1; k <= 2 * n; k++) {
			if (a[k] == 1)
				count++;
		}


		cout << count << '\n';


		cin >> n;
		if (n == 0)
			break;
	}

}