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.
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 read(f1,n); 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); read(f1,n); 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(); }
Code mẫu của ll931110
{$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 read(x); 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.
Comments