TIOJ 1036 How Many Primes?

[篩子+空間壓到N/2]

搞這題搞好久= = 最後毅然決然去壓空間，竟然AC了.....

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<vector>
#define MAX 10000000
using namespace std;
bool sieve[MAX/2+1];
int prime[664579];
int pcnt=0;
int bry(int a,int b,int r)
{
    if((r-1)*r==0)
        return 0;
    if(a==b)
        return a+1;
    if((a+1)==b)
    {
        if(prime[b]>r)
            return a+1;
        else
            return b+1;
    }

    int mid=(a+b)/2;
    if(prime[mid]>r)
        return bry(a,mid,r);
    else if(prime[mid]<r)
        return bry(mid,b,r);
    else
        return mid+1;
}
int g(int lx)
{
 if(lx==1)
  return 2;
 else
  return 2*lx-1;
}
int invg(int x){return (x+1)/2;}
int main()
{
    memset(sieve,true,sizeof(sieve));
    for (int lx=2; g(lx)*g(lx)<MAX; lx++)
  if (sieve[lx])
   for (int ly=3; g(lx)*ly<MAX; ly+=2)
                sieve[invg(g(lx)*ly)] = false;
    for(int lx=1;lx<MAX/2+1;lx++)
  if(sieve[lx])
   prime[pcnt++]=g(lx);
    free(sieve);
    int inp,in;scanf("%d",&inp);
    int min,max;

    for(int lx=1;lx<=inp;lx++)
    {
     scanf("%d",&in);
        min=floorf((double)(in)/(double)log2(in)/(double)3);
        max=ceilf((double)(in)/(double)log2(in)*(double)6);
        if(in>=100)
   max=ceilf((double)(in)/((double)log(in)-4));
  else
  {
   min=1;
   max=26;
  }
        if(min<=1) min=1;
        if((max>664578)||(max<0)) max=664578;
        printf("%d\n",bry(min,max,in));
    }
    return 0;
}