CPRIME - Prime Number Theorem
Tác giả: happyboy99x
Ngôn ngữ: C++
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1e8, NPRIME = 5761455;
int prime[NPRIME];
unsigned flag[N >> 6];
#define turnOn(p) (flag[p >> 6] |= 1 << ((p >> 1) & 31))
#define get(p) (flag[p >> 6] & (1 << ((p >> 1) & 31)))
void eratos() {
for(int i = 3; i * i <= N; i += 2) if(!get(i))
for(int j = i * i, d = i << 1; j <= N; j += d) turnOn(j);
int c = 1; prime[0] = 2;
for(int i = 3; i <= N; i += 2) if(!get(i)) prime[c++] = i;
}
int main() {
eratos();
for(int x; scanf("%d", &x) == 1 && x != 0; ) {
int pi = upper_bound(prime, prime + NPRIME, x) - prime;
printf("%.1lf\n", fabs((pi - x / log(x)) / pi * 100));
}
return 0;
}