题意：H-number: 所有4的倍数加1 如 1 5 9 13.....
H-prime: 因子除了1，没有其他因子为H-number
H-semi-prime: 只能拆成两个 H-prime的乘积，方案可以有多种，但只能拆成两个。
筛法，各种筛.....
1 Program poj3292; 2 3 const maxh=1000001 div 4+1; 4 5 var h,le,lq:longint; 6 7 a:array[1..maxh]of boolean; 8 9 p,q:array[1..maxh]of longint; 10 11 f:array[0..maxh]of longint; 12 13 14 Procedure initprimegram; 15 16 var i,j,k:longint; 17 18 begin 19 20 21 fillchar(a,sizeof(a),true); 22 23 24 for i:=1 to maxh do 25 26 if a[i] then 27 28 begin 29 30 inc(le); 31 32 p[le]:=i; 33 34 for j:=1 to maxh do 35 36 begin 37 38 if ((i*4+1)*(j*4+1)>(maxh+1)*4) then break; 39 40 if ((i*4+1)*(j*4+1)-1) mod 4=0 then 41 42 a[((i*4+1)*(j*4+1)-1) div 4]:=false; 43 44 end; 45 46 end; 47 48 for i:=1 to maxh do 49 50 if a[i]=false then begin inc(lq);q[lq]:=i;end; 51 52 fillchar(a,sizeof(a),false); 53 54 for i:=1 to le do 55 56 for j:=i to le do 57 58 begin 59 60 if (int64(p[i])*4+1)*(p[j]*4+1)>(maxh+1)*4 then break; 61 62 a[((p[i]*4+1)*(p[j]*4+1)-1) div 4]:=true; 63 64 end; 65 66 for i:=1 to lq do 67 68 for j:=1 to maxh do 69 70 begin 71 72 if (int64(q[i])*4+1)*(j*4+1)>(maxh+1)*4 then break; 73 74 a[((q[i]*4+1)*(j*4+1)-1)div 4]:=false; 75 76 end; 77 78 for i:=1 to maxh do 79 80 begin 81 82 if a[i] then f[i]:=f[i-1]+1 else f[i]:=f[i-1]; 83 84 end; 85 86 87 end; 88 89 90 Begin 91 92 assign(input,'input.in');assign(output,'output.out'); 93 94 reset(input);rewrite(output); 95 96 initprimegram; 97 98 readln(h); 99 100 while h<>0 do101 102 begin103 104 writeln(h,' ',f[h div 4]);105 106 readln(h);107 108 end;109 110 close(input);close(output);111 112 end.