Hướng dẫn giải của Prime Number Theorem
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
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.
Bình luận