294 - Divisors

[Ghust_omega]

Hi !! jhonny_yang I submit your code and gives TLE, but if you have to avoid you have to think about more, how to get the divisors of a number whitout find then
Hope it Helps
Keep posting !!

[jhonny_yang]

Today i try to using sqrt() like find the prime number

100 = 10 * 10

it's impossible divide the number large than 10 in this case. So you can add the range below than sqrt().

and then do this :

if (number%divisor==0){
Counter++;
if (number/divisor!=divisor)Counter++;
}

that so solve like 2*50 and no need to found 50*2 because our limit is 10.

i dunno this algorithm is acceptable or not because judge is down

[jhonny_yang]

Today i try to using sqrt() like find the prime number

100 = 10 * 10

it's impossible divide the number large than 10 in this case. So you can add the range below than sqrt().

and then do this :

if (number%divisor==0){
Counter++;
if (number/divisor!=divisor)Counter++;
}

that so solve like 2*50 and no need to found 50*2 because our limit is 10.

i dunno this algorithm is acceptable or not because judge is down

All i say is correct i acceptable

[eshika]

I got runtime error. Please help me.
I have precalculated prime numbers. Then computed the divisors for n where n =p1^e1* p2^e2* ... *pn^en equals (e1+1)*(e2+1)*...*(en+1).

Code: Select all

#include<math.h>
#include<stdio.h>

int Isprime(int I);

int primes[10000]={2};
long double lu;
unsigned long max,sum,j,p,N,d,LU,pm=1,i,U,L;

void main()
{
 lu=sqrt(1000000000);
 LU=lu;
 for(p=0,i=3;i<=LU;i+=2)
    if(Isprime(i)) primes[pm++]=i;
 scanf("%lu",&N);
 while(N>0)
 {
  max=0;
  scanf("%lu%lu",&L,&U);
  {
   for(i=L;i<=U;i++)
   {
	d=1;
	if(i==1) d=1;
	pm=0;j=i;
	while(j!=1)         
	{
	  sum=0;
	  while(j%primes[pm]==0)
	  {
		j=j/primes[pm];
		sum++;
	  }
	  pm++;
	  if(sum>0)  d=d*(sum+1);
	}
	if(d>max){
		  max=d;
		  p=i;
		 }

   }
  }
  printf("Between %lu and %lu, %lu has a maximum of %lu divisors.\n",L,U,p,max);
  N--;
 }
}

int Isprime(int I)
{
   int n;
   for(n=2;n<I;n++)
	  if((I%n)==0)	 return 0;
   return 1;
}

[Evan Tsang]

You got division by zero in this line while(j%primes[pm]==0)

[CodeMaker]

I think if you solve the runtime error problem, you have a great chance of getting Time limite exeted.

to find primes you can use the method of seive.

then you also will be able to find the divisors without any extra calculations.

[eshika]

Thanks all of you to response.
I haven’t worked yet.
As far as I know sieve method is efficient for generating primes upto 1 million (1000000) only. But in this problem L and U are chosen such that 1<=L<=U<=1000000000.
Should I use sieve method for this problem?

[Iwashere]

you do not need sieve. infact you do not even need to find primes at all. there is a much simpler way of dividing a number with primes...

[eshika]

infact you do not even need to find primes at all.

Would you please explain in more detail?

[alu_mathics]

well you only need to generate primes up to sqrt(1000000000).
why ? try to think abt it.you will find it by yourself.
best of luck.

[Antonio Ocampo]

Yeah you only need generate primes for 1 to sqrt(10^9). And if you don't use sieve, probably you get TLE.

Best regards

[elmedin]

Here is my code. I don't know what is wrong with it. Please help.

Code: Select all

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
   int N, L, H, P = 0, D = 0;
   double nesto;
   int divisors = 0;
   
   cin >> N;
   for(int i = 0; i < N; i++)
   {
      cin >> L >> H;
      for(int j = L; j <= H; j++)
      {
         divisors = 0;
         nesto = sqrt(j);
         for(int l = 1; l <= nesto; l++)
         {
            if(!(j%l))
               divisors += 2;
            if(nesto * nesto == j)
               divisors--;
         };
         if(D < divisors)
         {
            D = divisors;
            P = j;
         }
      };
      cout << "Between " << L << " and " << H << ", " << P << " has a maximum of " << D <<" divisors." << endl;
      D = 0;
   };
   return 0;
};

[mf]

Your code which counts divisors sometimes gives wrong answers. For example, 1000000 has 49 divisors, but your code counted -950 (!).

[elmedin]

Thank you very much mf. I got AC.

[marcadian]

I have tested it many times,but it still got WA, please help me

Code: Select all

program divisor294;
var     n,i,l,k,temp,m,o,p,max,kand,a,j,t:longword;
begin
        readln(k);
        for j:=1 to k do
        begin
                readln(m,o);
                kand:=m;
                max:=0;
                for a:=m to o do
                begin
                 t:=0;
                 temp:=1;
                 n:=a;
                 l:=round(sqrt(n));
                 while n mod 2=0 do
                 begin
                        n:=n shr 1;
                        inc(t);
                 end;
                 temp:=temp*(t+1);
                 i:=3;
                 t:=0;
                 while (n>1) do
                 begin
                        if i>l then break;
                        if (n mod i=0) then
                        begin
                                n:=n div i;
                                inc(t);
                        end;
                        if (n mod i<>0) then
                        begin
                                temp:=temp*(t+1);
                                inc(i,2);
                                t:=0;
                        end;
                 end;
                 if (temp=1) then temp:=2;

                 if temp>max then
                 begin
                       max:=temp;
                       kand:=a;
                 end;
                 if kand=1 then max:=1;
                 end;
         writeln('Between ',m,' and ',o,', ',kand,' has a maximum of ',max,' divisors.');
         end;
end.