[Algorithm/C] BOJ.4948 베르트랑 공준
Bertrands_postulate.cClick to download.
접근방법
1. 지금까지 해왔던 isPrime 함수를 그대로 사용.
2. 시간이 조금 걸렸던 이유는 변수의 존재 범위에 따라 답이 다르게 나옴.
/*
https://www.acmicpc.net/problem/4948
Bertrand's postulate
Writer : Mun Jae In
Date : 2017.12.16
*/
#include <stdio.h>
#include <math.h>
int isPrime(int n)
{
if(n==1)
{
return 0;
}
else if(n<4)
{
return 1;
}
else if(n%2==0)
{
return 0;
}
else if(n<9)
{
return 1;
}
else if(n%3==0)
{
return 0;
}
else
{
double r = floor(sqrt((double)n));
int f = 5;
while (f<=r)
{
if(n%f==0)
{
return 0;
}
else if(n%(f+2)==0)
{
return 0;
}
f += 6;
}
return 1;
}
}
int main(int argc, char * argv[])
{
int n = 0;
while(1)
{
scanf("%d",&n);
if(n==0){
break;
}
else
{
int limit = 2*n;
int count = 0;
while(1)
{
if(isPrime(++n))
{
count++;
}
if(n==limit){
printf("%d\n",count);
break;
}
}
}
}
return 0;
}