11960 - Divisor Game

[plamplam]

Sure thing I don't mind sharing but I thought you got AC (from the above posts). Why bother with this problem? If you still want to know what my solution is then PM me with your email.

[mahade hasan]

hy I think prime factorization needs more time so i try this .....
But get TLE.....Any one plz help me...........plz

Code: Select all

#include<stdio.h>
#include<math.h>
long Number[1000009]={0,1};

void Cal()
{
   long I,K,N;
   for(I=2;I<1000001;I++)
   {
      for(K=(double)sqrt(I);K>1;K--)
      {
         if(I%K==0)
         {
            N=I/K;
            if(N==K) ++Number[I];
            else Number[I]+=2;
         }         
      }
      Number[I]+=2;
   }
}

int main()
{
   long I,K,L,M,N,Test;
   Cal();
   
   scanf("%ld",&Test);
   for(;Test>0;Test--)
   {
      L=1;M=1;
      scanf("%ld",&N);
      for(I=N;I>1;I--)
      if(Number[I]>M)
      {
         M=Number[I];
         L=I;
      }
      printf("%ld\n",L);
      
   }
   return 0;
}

[/color]

[brianfry713]

First precompute the primes.

[Faithkeeper_Rangwan]

I don't think this problem even need to use prime factorization.

[Zyaad Jaunnoo]

I don't think this problem even need to use prime factorization.

I modified the sieve of Eratosthenes to count the number of divisors for all N <= 1,000,000.