- Total
꿈꾸는리버리
[백준 알고리즘 4948] 베르트랑 공준 본문
https://www.acmicpc.net/problem/4948
4948번: 베르트랑 공준
베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼
www.acmicpc.net

풀이방법 : 해당 수의 제곱근까지만 나누어보는 것 && 에라토스테네스의 체 (백준 1929 소수구하기 문제와 동일)
에라토스테네스의 체를 사용해야 하는 이유는 시간초과 때문이다. 소수를 판별하기 위해서 이전의 수를 모두 나누어보는 것은 시간복잡도가 엄청나게 커지는 방법이기 때문이다.
해당 수의 제곱근까지만 나누어보는 것:
쉽게 생각해보자. 예를 들어 18의 소수를 구하려고 한다. 1,2,3,4,5,6,7,8,...,18 -> 루트 18은 대략 4. xx이다.
만약 4(루트 18) 보다 큰 소인수가 있다면 이미 그 짝은 4보다 작은 수일 것이다. ex) (4보다 큰 소인수 == 6 )-> (6의 짝 == 3)
그러니 이미 순차적으로 i를 증가시키는 동안 이미 4보다 작은 수로(3으로) 나누어보았을 것이다.
에라토스테네스의 체:
이름부터 어려운 에라토스테네스...의 체... 원리는 easy하다. 이전에 든 예 18로 계속 진행을 해보겠다.
1,2,3,4,5,6,7,8,...,18 에서 일단 소수가 될 수 없는 1을 빼고, 다음 수인 2가 소수인지 판별한다.
2가 소수네 ? --> 2를 제외한 2의 배수 다 삭제 : 2,3,5,7,9,11,13,15,17
2 다음 수인 3이 소수인지 판별한다.
3이 소수네 ? --> 3을 제외한 3의 배수 다 삭제 : 2,5,7,11,13,17
~~ 해서 18일 때까지 반복을 하면 된다.
작성한 코드는 다음과 같다.
#include <iostream>
#include <math.h>
using namespace std;
void Count(int N){
if(N == 0 ) return;
int array[N];
int count = 0;
for( int i = 0 ; i < N+1; i++){
array[i] = i;
}
array[1] = 0;
for(int i = 2 ; i < sqrt(N+1); i++){
if(array[i] >= 1){
for(int k = i*i ; k < N+1; k = k+i){
array[k] = 0;
}
}
}
for(int i = N/2+1 ; i < N+1; i++){
if(array[i] >= 1){
count ++;
}
}
cout << count << "\n";
return;
}
int main() {
int N;
while(1){
cin >> N;
Count(2*N);
if( N == 0 ) break;
}
return 0;
}
성공한 사진 !

'오뚝이 개발자 > 알고리즘' 카테고리의 다른 글
[백준 알고리즘] 3009 네 번째 점 (0) | 2021.12.01 |
---|---|
[백준 알고리즘] 1085 직사각형에서 탈출 (0) | 2021.12.01 |
[백준 알고리즘] 9020 골드바흐의 추측 C++ (0) | 2021.12.01 |
[백준 알고리즘 11653] 소인수분해 (0) | 2021.11.30 |
[백준 알고리즘] 1929 소수구하기 C++ (0) | 2021.11.30 |