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
      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

Please read the guidelines before commenting.


There are no comments at the moment.