백준
백준 소스코드 [C++] 4948 베르트랑 공준
Hani_Levenshtein
2020. 8. 18. 23:59
https://www.acmicpc.net/problem/4948
4948번: 베르트랑 공준
문제 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 ��
www.acmicpc.net
백준 소스코드 [C++] 4948 베르트랑 공준
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int b = 123456*2;
bool* arr = new bool[b+1];
for (int i = 2;i <= b;i++) arr[i] = true;
for (int i = 2;i <= sqrt(b);i++)
if (arr[i])
for (int j = i + i;j <= b;j = j + i)arr[j] = false;
int n;
while (true) {
cin >> n;
if (n == 0) break;
int stack = 0;
for (int i = n+1;i <= 2 * n;i++) if (arr[i] == true) stack++;
cout << stack << '\n';
}
return 0;
}