294 - Divisors

All about problems in Volume 2. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

User avatar
Ghust_omega
Experienced poster
Posts: 115
Joined: Tue Apr 06, 2004 7:04 pm
Location: Venezuela

Post by Ghust_omega » Sun Oct 10, 2004 3:01 am

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 !! :D

jhonny_yang
New poster
Posts: 22
Joined: Fri Jan 17, 2003 8:24 am

Re: Cul de sac.

Post by jhonny_yang » Fri Nov 12, 2004 5:22 am

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
New poster
Posts: 22
Joined: Fri Jan 17, 2003 8:24 am

Re: Cul de sac.

Post by jhonny_yang » Fri Nov 12, 2004 8:48 am

jhonny_yang wrote: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
New poster
Posts: 11
Joined: Sat Oct 02, 2004 12:02 pm
Location: Bangladesh

294:DIVISORS...RUNTIME ERROR...PLEASE HELP!!!!!!!

Post by eshika » Tue Jan 04, 2005 10:19 am

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
New poster
Posts: 11
Joined: Sun Jan 02, 2005 9:14 am

Post by Evan Tsang » Tue Jan 04, 2005 11:15 am

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

User avatar
CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
Location: AIUB, Bangladesh

Post by CodeMaker » Thu Jan 06, 2005 4:16 pm

:-? 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.
Jalal : AIUB SPARKS

eshika
New poster
Posts: 11
Joined: Sat Oct 02, 2004 12:02 pm
Location: Bangladesh

Post by eshika » Sun Jan 09, 2005 11:07 am

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
New poster
Posts: 20
Joined: Mon Aug 11, 2003 1:50 pm
Location: Singapore

Post by Iwashere » Sun Jan 09, 2005 4:32 pm

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
New poster
Posts: 11
Joined: Sat Oct 02, 2004 12:02 pm
Location: Bangladesh

Post by eshika » Tue Jan 11, 2005 11:01 am

infact you do not even need to find primes at all.
Would you please explain in more detail?

User avatar
alu_mathics
Learning poster
Posts: 55
Joined: Sat Jan 24, 2004 9:30 pm
Location: Chittagong
Contact:

Post by alu_mathics » Wed Jan 12, 2005 1:52 am

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.
cuii e

Antonio Ocampo
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per

Post by Antonio Ocampo » Sun Jan 16, 2005 8:11 pm

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
New poster
Posts: 3
Joined: Wed Apr 13, 2005 7:30 pm

294 - Divisors WA!!!

Post by elmedin » Mon May 23, 2005 1:15 am

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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Mon May 23, 2005 5:53 am

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

elmedin
New poster
Posts: 3
Joined: Wed Apr 13, 2005 7:30 pm

Post by elmedin » Wed Jun 01, 2005 10:16 pm

Thank you very much mf. I got AC.

marcadian
New poster
Posts: 45
Joined: Sun Jun 26, 2005 6:21 am
Contact:

Divisors-294 WA

Post by marcadian » Sun Jun 26, 2005 6:36 am

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.

Post Reply

Return to “Volume 2 (200-299)”