## Editorial for Prime Number Theorem

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

#### Code mẫu của flashmt

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <bitset>
#include <cmath>
using namespace std;

bitset<100000100> d;
int p[6000000],P;

int main()
{
for (int i=2;i*i<100000000;i++)
if (!d[i])
for (int j=i*i;j<100000000;j+=i)
d[j]=1;
for (int i=2;i<100000000;i++)
if (!d[i])
p[P++]=i;

int n;
while (scanf("%d",&n), n)
{
int num=upper_bound(p,p+P,n)-p;
printf("%.1lf\n",100.0*fabs(num-n/log(n))/num);
}
}


#### Code mẫu của happyboy99x

#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;
}


#### Code mẫu của RR

{$R-,Q-} {$Mode objFPC}
uses math,crt;
const
FINP          =       '';
FOUT          =       '';
MAXN          =       100000;
cprime        :       array[0..1000] of longint=(0,
9592,17984,25997,33860,41538,49098,56543,63951,71274,78498,85714,92938,100021,107126,114155,121127,128141,135072,142029,148933,
155805,162662,169511,176302,183072,189880,196645,203362,210109,216816,223492,230209,236900,243539,250150,256726,263397,269987,276611,283146,
289774,296314,302824,309335,315948,322441,328964,335439,341992,348513,354971,361407,367900,374362,380800,387202,393606,399993,406429,412849,
419246,425648,432073,438410,444757,451159,457497,463872,470283,476648,483015,489319,495666,501962,508261,514565,520910,527154,533506,539777,
546024,552319,558597,564877,571119,577439,583714,590006,596222,602489,608672,614917,621177,627400,633578,639851,646054,652265,658445,664579,
670820,676970,683178,689382,695609,701795,708007,714154,720341,726517,732707,738873,745001,751131,757288,763455,769639,775773,781906,788060,
794149,800285,806435,812601,818703,824801,830940,837099,843192,849252,855281,861401,867482,873606,879640,885698,891833,897938,904057,910077,
916147,922193,928293,934441,940455,946551,952566,958651,964695,970704,976761,982776,988851,994839,1000862,1006966,1013012,1019012,1025092,1031130,
1037119,1043113,1049172,1055139,1061198,1067185,1073198,1079266,1085243,1091314,1097360,1103258,1109288,1115323,1121389,1127407,1133364,1139344,1145305,1151367,
1157275,1163205,1169267,1175214,1181158,1187148,1193122,1199102,1205065,1211050,1216988,1222953,1228861,1234873,1240833,1246718,1252693,1258685,1264617,1270607,
1276577,1282513,1288409,1294356,1300243,1306226,1312179,1318125,1324046,1329943,1335881,1341795,1347749,1353661,1359631,1365511,1371432,1377385,1383291,1389261,
1395148,1401007,1406874,1412758,1418640,1424606,1430531,1436398,1442335,1448221,1454144,1460019,1465935,1471822,1477731,1483609,1489509,1495350,1501220,1507122,
1512992,1518898,1524831,1530729,1536569,1542459,1548366,1554245,1560093,1565927,1571812,1577649,1583439,1589324,1595177,1601049,1606876,1612775,1618668,1624527,
1630379,1636202,1642052,1647911,1653807,1659690,1665517,1671330,1677200,1683065,1688960,1694762,1700558,1706405,1712204,1718134,1723913,1729764,1735590,1741430,
1747297,1753058,1758964,1764767,1770613,1776430,1782260,1788065,1793863,1799676,1805472,1811272,1817102,1822944,1828703,1834530,1840359,1846115,1852006,1857859,
1863719,1869536,1875367,1881199,1886923,1892785,1898632,1904396,1910248,1915979,1921714,1927488,1933290,1939089,1944833,1950638,1956440,1962184,1968015,1973815,
1979564,1985372,1991162,1996958,2002749,2008561,2014337,2020103,2025864,2031667,2037385,2043192,2048989,2054802,2060577,2066324,2072084,2077862,2083678,2089379,
2095092,2100791,2106544,2112215,2118001,2123788,2129473,2135232,2141013,2146775,2152470,2158233,2163998,2169775,2175518,2181266,2187043,2192806,2198505,2204262,
2210026,2215731,2221543,2227279,2233036,2238778,2244473,2250226,2255897,2261623,2267395,2273189,2278857,2284633,2290350,2296101,2301840,2307562,2313254,2318966,
2324728,2330509,2336299,2342005,2347727,2353448,2359142,2364953,2370696,2376402,2382120,2387828,2393630,2399359,2405101,2410827,2416624,2422305,2427981,2433654,
2439371,2445078,2450819,2456577,2462273,2467902,2473603,2479409,2485075,2490756,2496476,2502205,2507850,2513534,2519246,2524898,2530575,2536286,2542018,2547620,
2553305,2559020,2564807,2570490,2576200,2581841,2587550,2593245,2598870,2604535,2610226,2615907,2621566,2627281,2632997,2638710,2644301,2649982,2655643,2661384,
2667036,2672702,2678429,2684053,2689717,2695450,2701159,2706858,2712494,2718160,2723886,2729508,2735255,2740985,2746679,2752380,2758056,2763691,2769407,2775053,
2780731,2786355,2791974,2797652,2803324,2808976,2814698,2820355,2826040,2831693,2837271,2842995,2848642,2854302,2859963,2865596,2871207,2876824,2882545,2888144,
2893763,2899408,2905025,2910714,2916338,2921977,2927626,2933208,2938896,2944531,2950188,2955834,2961491,2967186,2972862,2978556,2984185,2989825,2995509,3001134,
3006727,3012361,3018013,3023649,3029296,3034973,3040593,3046241,3051875,3057494,3063082,3068712,3074341,3080043,3085615,3091310,3096885,3102560,3108210,3113843,
3119506,3125086,3130647,3136324,3141927,3147521,3153171,3158801,3164431,3170052,3175695,3181277,3186966,3192556,3198119,3203713,3209317,3214948,3220576,3226203,
3231825,3237408,3242981,3248574,3254129,3259801,3265418,3271006,3276528,3282200,3287879,3293449,3299022,3304658,3310266,3315819,3321475,3327111,3332731,3338330,
3343958,3349661,3355218,3360782,3366339,3371952,3377626,3383274,3388854,3394435,3400038,3405629,3411294,3416918,3422475,3428077,3433631,3439220,3444790,3450336,
3455970,3461542,3467134,3472756,3478304,3483945,3489523,3495161,3500795,3506314,3511921,3517468,3523035,3528547,3534167,3539757,3545331,3550955,3556550,3562115,
3567677,3573237,3578833,3584453,3590054,3595578,3601204,3606812,3612449,3618045,3623569,3629084,3634647,3640201,3645798,3651314,3656875,3662428,3668016,3673600,
3679207,3684787,3690317,3695916,3701487,3707015,3712576,3718206,3723740,3729306,3734871,3740435,3746021,3751585,3757186,3762745,3768288,3773903,3779511,3785086,
3790643,3796205,3801803,3807345,3812898,3818389,3823937,3829432,3835002,3840554,3846130,3851637,3857201,3862694,3868404,3873874,3879427,3884940,3890503,3896123,
3901727,3907301,3912842,3918498,3924009,3929584,3935172,3940685,3946251,3951767,3957296,3962821,3968429,3973996,3979592,3985158,3990671,3996215,4001767,4007342,
4012851,4018394,4023969,4029474,4035037,4040549,4046077,4051617,4057149,4062674,4068213,4073713,4079200,4084816,4090382,4095945,4101517,4107066,4112568,4118064,
4123596,4129144,4134695,4140216,4145831,4151356,4156813,4162309,4167847,4173373,4178911,4184419,4189971,4195467,4201083,4206661,4212176,4217594,4223154,4228658,
4234244,4239815,4245417,4250930,4256409,4261935,4267454,4272940,4278523,4284089,4289594,4295059,4300577,4306121,4311581,4317182,4322713,4328194,4333750,4339254,
4344668,4350186,4355687,4361240,4366707,4372244,4377733,4383283,4388818,4394304,4399810,4405341,4410890,4416431,4421976,4427436,4432986,4438498,4444056,4449611,
4455090,4460606,4466047,4471575,4477022,4482514,4487991,4493463,4498996,4504535,4510062,4515582,4521040,4526576,4532043,4537551,4543006,4548526,4554051,4559544,
4565039,4570576,4576018,4581510,4586928,4592508,4597955,4603527,4608972,4614444,4619984,4625476,4630913,4636426,4641948,4647416,4652931,4658438,4663931,4669382,
4674878,4680315,4685896,4691370,4696907,4702361,4707853,4713384,4718907,4724409,4730004,4735525,4740992,4746465,4752027,4757470,4762951,4768393,4773922,4779430,
4784949,4790384,4795812,4801310,4806760,4812305,4817816,4823303,4828831,4834317,4839761,4845183,4850683,4856110,4861617,4867093,4872513,4878005,4883558,4889139,
4894521,4899985,4905417,4910914,4916472,4921878,4927326,4932826,4938246,4943731,4949180,4954637,4960077,4965591,4971111,4976569,4982049,4987530,4993012,4998470,
5003979,5009407,5014862,5020351,5025823,5031315,5036777,5042265,5047761,5053180,5058696,5064123,5069614,5075035,5080463,5085953,5091415,5096846,5102346,5107832,
5113355,5118791,5124356,5129773,5135232,5140593,5146076,5151557,5157086,5162565,5167986,5173502,5178996,5184377,5189833,5195242,5200653,5206040,5211514,5216954,
5222465,5227980,5233446,5238910,5244409,5249827,5255274,5260749,5266190,5271659,5277103,5282580,5288120,5293544,5298991,5304404,5309926,5315370,5320738,5326237,
5331696,5337154,5342570,5348001,5353469,5358873,5364374,5369836,5375312,5380681,5386095,5391573,5396981,5402486,5407914,5413340,5418747,5424169,5429670,5435104,
5440645,5446042,5451511,5456922,5462365,5467823,5473280,5478704,5484246,5489749,5495144,5500596,5506042,5511482,5516967,5522414,5527834,5533229,5538712,5544201,
5549568,5555003,5560413,5565874,5571310,5576734,5582247,5587668,5593068,5598565,5604003,5609349,5614798,5620231,5625732,5631229,5636652,5642089,5647525,5652996,
5658353,5663763,5669215,5674668,5680084,5685585,5691004,5696344,5701777,5707123,5712622,5718013,5723380,5728833,5734258,5739704,5745162,5750539,5756001,5761455);

var
f1,f2         :       text;
sang          :       array[1..MAXN] of longint;
prime         :       array[1..MAXN] of longint;
sprime        :       longint;
n             :       longint;

procedure openF;
begin
assign(f1,FINP); reset(f1);
assign(f2,FOUT); rewrite(f2);
end;
procedure closeF;
begin
close(f1);
close(f2);
end;
procedure generate;
var
i,j:longint;
begin
sang[1]:=1;
for i:=2 to MAXN do
if sang[i]=0 then
begin
inc(sprime);
prime[sprime]:=i;
j:=i+i;
while (j<=MAXN) do
begin
sang[j]:=1;
inc(j,i);
end;
end;
end;
function isPrime(n:longint):boolean;
var
i,gh:longint;
begin
if n=1 then exit(false);
gh:=trunc(sqrt(n));
for i:=1 to sprime do
begin
if prime[i]>gh then exit(true);
if n mod prime[i]=0 then exit(false);
end;
end;
procedure bua;
var
start,finish,doan,i,count:longint;
begin
count:=sprime; write(f2,count,',');
for doan:=2 to 1000 do
begin
start:=(doan-1)*MAXN+1;
finish:=doan*MAXN;
for i:=start to finish do
if isPrime(i) then inc(count);
write(f2,count,',');
if doan mod 20=0 then writeln(f2);
if keypressed then begin closeF; halt; end;
end;
end;
procedure update(start,last:longint; var count:longint);
var
i,j,size,x:longint;
begin
fillchar(sang,sizeof(sang),0);
if not isPrime(start) then sang[1]:=1;
size:=last-start+1;
for i:=1 to sprime do
if prime[i]<=size then
begin
x:=prime[i]-start mod prime[i]+1;
if start=1 then inc(x,prime[i]);
while x<=size do
begin
sang[x]:=1;
inc(x,prime[i]);
end;
end
else break;
for i:=1 to size do
if sang[i]=0 then inc(count);
end;
procedure solve;
var
count,i,start,seg,module:longint;
begin
while (n>0) do
begin
seg:=n div MAXN; module:=n mod MAXN;
if module=0 then count:=cprime[seg]
else
begin
count:=cprime[seg];
start:=MAXN*seg+1;
update(start,n,count);
end;
writeln(f2,abs(count-n/ln(n))*100/count:0:1);
end;
end;

begin
openF;
generate;
//  bua;
solve;
closeF;
end.


#### Code mẫu của hieult

#include <cstdio>
//#include <conio.h>
#include <math.h>
#define lon 100000000
#define doc(n) ( bpc[n/8]&(1<<(n%8)))
#define set(n) { bpc[n/8]|=(1<<(n%8));}
int bpc[6500000];

int main()
{
// freopen("CPRIME.in","r",stdin);
set(0);
for(int i = 3;i*i<= lon;i+=2)
{
if(!doc(i/2))
{
for(int j = i*i;j<=lon;j+=2*i){set(j/2);}
}
}
int a[1010],vt[1010],so=0,temp,pi[1010],m;
while(scanf("%d",&a[++so])>0&&a[so]>0);
so--;
for(int i = 1;i<=so;i++)
vt[i] = i;
for(int i = 1;i<=so;i++)
for(int j = i+1;j<=so;j++)
{
if(a[i]>a[j])
{
temp = a[i];
a[i] = a[j];
a[j] = temp;
temp = vt[i];
vt[i] = vt[j];
vt[j] = temp;
}
}
int n = 2,chay = 1;
for(int i = 1;i<=so;i++)
{
while(n<a[i])
{
n++;
if((n%2)&&!doc(n/2))
chay++;
}
pi[i] = chay;
}
for(int i = 1;i<=so;i++)
for(int j = i+1;j<=so;j++)
{
if(vt[i]>vt[j])
{
temp = vt[i];
vt[i] = vt[j];
vt[j] = temp;
temp = pi[i];
pi[i] = pi[j];
pi[j] = temp;
temp = a[i];
a[i] = a[j];
a[j] = temp;

}
}
for(int i = 1;i<=so;i++)
printf("%.1lf\n",fabs((pi[i]-a[i]/log(a[i]))/(0.01*pi[i])));
// getch();
}


{$MODE DELPHI} Program CPRIME2; Const input = ''; output = ''; maxn = 50000000; Var fi,fo: text; a: array[1..maxn] of boolean; p: array[1..6000000] of integer; num: integer; Procedure openfile; Begin Assign(fi, input); Reset(fi); Assign(fo, output); Rewrite(fo); End; Procedure gens; Var i,k,t: integer; Begin num:= 1; p[1]:= 2; Fillchar(a, sizeof(a), true); For i:= 1 to maxn do if a[i] then Begin t:= 2 * i + 1; inc(num); p[num]:= t; k:= i; While k <= maxn do Begin k:= k + t; If k <= maxn then a[k]:= false; End; End; End; Function search(x: integer): integer; Var inf,sup,med,r: integer; Begin inf:= 1; sup:= num; r:= 0; Repeat med:= (inf + sup) shr 1; If x = p[med] then exit(med); If x > p[med] then Begin r:= med; inf:= med + 1; End else sup:= med - 1; Until inf > sup; search:= r; End; Procedure solve; Var t,x: integer; val: real; Begin Repeat Readln(fi, x); If x = 0 then break; t:= search(x); val:= abs((t - x /ln(x))) / t * 100; Writeln(fo, val:0:1); Until x = 0; End; Procedure closefile; Begin Close(fo); Close(fi); End; Begin openfile; gens; solve; closefile; End.  #### Code mẫu của khuc_tuan // {$APPTYPE CONSOLE}
{\$mode delphi}

uses math, sysutils;

const
max = 100000000;
max2 = 10000;

var
ip : array[0..max] of boolean;
p : array[0..6000000] of integer;
le, ri, mi, np : integer;
n, x, y, x2, y2 : integer;

begin

ip[2] := true;
ip[3] := true;

for x := 1 to max2 do
begin
x2 := x * x;
for y := 1 to max2 do
begin
y2 := y * y;
n := 4 * x2 + y2;
if (n <= max) and ((n mod 12 = 1) or (n mod 12 = 5)) then
ip[n] := not ip[n];
dec(n, x2);
if (n <= max ) and (n mod 12 = 7) then
ip[n] := not ip[n];

dec(n, y2); dec(n, y2);
if (x>y) and (n<=max) and (n mod 12 = 11) then
ip[n] := not ip[n];
end;
end;

for n:=5 to max2 do
if ip[n] then
begin
x := n * n;
y := x;
while y <= max do
begin
ip[y] := false;
inc( y, x);
end;
end;

np := 0;

for n:=2 to max do
if ip[n] then
begin
inc(np);
p[np] := n;
end;

// writeln(np);

while true do
begin
if x=0 then break;
le := 1;
ri := np;
while le < ri do
begin
mi := (le+ri) div 2 + 1;
if p[mi] > x then ri := mi - 1
else le := mi;
end;
writeln( (abs(le - x / ln(x)) / le * 100) :0 :1);
end;

end.