## 294 - Divisors

Moderator: Board moderators

pc5971
New poster
Posts: 34
Joined: Mon Aug 05, 2002 11:24 am
Contact:
Now I use your ideea (to precalculate the prime numbers) and I obtained a better result, 0.367s. I think that it's good enough for the moment... Thanks a lot

Jalal
Learning poster
Posts: 65
Joined: Sun Jun 02, 2002 8:41 pm
Contact:
There may be another problem in ur programs output
all the time u printed:
printf("Between %d and %d, %d has a maximum of %d divisors.n",inicio,fim,maior_n,maior);

But what is .n?
it will be \n for the new line.
cheak it once again.

kenny1har
New poster
Posts: 7
Joined: Fri May 09, 2003 2:30 am

### 294 - Divisors

[pascal]
program p294;
var
i,j,n,x,y,xtemp,ytemp,max,now,num:longint;
divisor:array[1..100000] of byte;

function scan(x:longint):longint;
var i,sum,limit:longint;
begin
i:=2;
limit:=trunc(sqrt(x))+1;
while x>1 do begin
while frac(x/i)<0.00000001 do begin
x:=x div i;
inc(divisor);
end;
inc(i);
if i>limit then break;
end;
sum:=1;
for i:=1 to limit do begin
if divisor<>0 then begin
sum:=sum*(divisor+1);
divisor:=0;
end;
end;
scan:=sum;
end;

begin
for i:=1 to n do begin
if x>y then begin
xtemp:=y;
ytemp:=x;
end
else begin
xtemp:=x;
ytemp:=y;
end;
max:=2;
fillchar(divisor,sizeof(divisor),0);
for j:=ytemp downto xtemp do begin
now:=scan(j);
if now>=max then begin
max:=now;
num:=j;
end;
end;
writeln('Between ',x,' and ',y,', ',num,' has a maximum of ',max,' divisors.');
end;
end.
[/pascal]

I have tried 3 times, but I can't get the correct answer.

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
Always try borderline cases:

Code: Select all

``````1
1 1
``````

Code: Select all

``````Between 1 and 1, 0 has a maximum of 2 divisors.
``````

epsilon0
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.
there is a smarter solution.

you don't need to try every divisor for a number n.

if you know its prime factors, it's easy then to compute the number of divisors.

so all you really need is a list of prime numbers (which you compute only once), then you can get prime factors of any number quickly.
We never perform a computation ourselves, we just hitch a ride on the great Computation that is going on already. --Tomasso Toffoli

Joseph Kurniawan
Experienced poster
Posts: 136
Joined: Tue Apr 01, 2003 6:59 am
Location: Jakarta, Indonesia
Using prime factors???
Could you please tell me more detail?
For instance:
9000 = 2 * 2 * 2 * 3 * 3 * 5 * 5 * 5
i.e. 9000 has 3 2's, two 3's and three 5's.
How do we compute the divisors of 9000??
Thanx !!
There are 3 things one need to be successful : motivation, ability and chance. And if you're a believer, make it four : God's will.

Cosmin.ro
Learning poster
Posts: 95
Joined: Thu Aug 21, 2003 12:02 am
The number of divisors of X=(p1^i1)*(p2^i2)*...*(pn^in) equals (i1+1)*(i2+1)*...*(in+1). You can prove this using induction or by observing that a divisor of X, y = (p1^j1)*(p2^j2)*...*(pn^jn) where 0<=j1<=i1,..., 0<=jn<=in. This is basic number theory, I think you can find this and more in CLR or any number theory book.

Joseph Kurniawan
Experienced poster
Posts: 136
Joined: Tue Apr 01, 2003 6:59 am
Location: Jakarta, Indonesia
Thanx a lot for the tips, cosmin.ro!!!
There are 3 things one need to be successful : motivation, ability and chance. And if you're a believer, make it four : God's will.

nonstop
New poster
Posts: 14
Joined: Fri Oct 03, 2003 5:13 am

### In 294,if two numbers have the same number of divisors....

how should i output my result???
thanks!

UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:
For each range, find the number P which has the largest number of divisors (if several numbers tie for first place, select the lowest)...

nonstop
New poster
Posts: 14
Joined: Fri Oct 03, 2003 5:13 am

### ...

As the number growing up, i need more time to get result.
But I have used the prime's method....
So,Is there any aspect i have not notice???

nonstop
New poster
Posts: 14
Joined: Fri Oct 03, 2003 5:13 am

### 294 WA.....i don't know why!!!.........

Code: Select all

``````[cpp]
#include<iostream.h>
#include<math.h>
struct divisor{
int factor;
int num;
};

bool prime(int X)
{
int i;
i=0;
for(i=2;i<X;i++)
if((X%i)==0)
return false;
return true;
}
int division(int div[],int X,int div_num)
{
int i=0,N=1,t=0;
int X2=X;
if(X==1)
return 1;
for(i=0;i<div_num;i++)
{
t=0;
while(X%div[i]==0)
{
X/=div[i];
t++;
}
if (t!=0)
N*=(t+1);
if(i>sqrt(X2))
{
N*=2;
break;
}
if(X==1)
break;
}
return N;
}
void main()
{
int div[10000];
int X,time,L,U,max=1,num=0,div_num=0,L2;
int i,j;
double k;
k=sqrt(1000*1000*1000)+1000;
j=k;
for(i=2;i<=j;)
{
if(prime(i))
div[div_num++]=i;
if(i==2)
i++;
else
i+=2;
}

cin>>time;
while(time>0)
{
max=1;
num=0;
i=j=X=0;
if((cin>>L>>U)&&(L<=U)&&(L>=1)&&(U<=1000000000))
{

for(i=L;i<=U;i++)
{
j=division(div,i,div_num);

if(j>max)
{
max=j;
X=i;
}

}

cout<<"Between "<<L<<" and "<<U<<", "<<X<<" has a maximum of "<<max<<" divisors."<<endl;
}
time--;
}

}
[/cpp]``````
.....................................
i can't find what's wrong.....

Arm.Turbo
New poster
Posts: 21
Joined: Wed Aug 11, 2004 1:20 pm
1 have 1 divisor (after i add this case i got AC)

Ndiyaa ndako
New poster
Posts: 21
Joined: Sat Sep 25, 2004 3:35 am
Location: Oaxaca de Ju
Contact:

### Cul de sac.

My program from the very begining used all those tricks. Anyway, I get Wrong Answer. I think it is because of the input reading

[c]
int main()
{
unsigned long factores(unsigned long);
unsigned long k,n,max,i,u,q,a,l;
scanf("%ld",&l);
for(a=0;a<l;a++)
{
scanf("%ld", &k);
scanf("%ld", &n);
max=factores(k);
q=k;
for(i=n;i>=k;i--)
{
u=factores(i);
if(u>=max)
{
max=u;
q=i;
}
}
printf("Beetween %ld and %ld, %ld has a maximum of %ld divisors.\n",k,n,q,max);
}
return 0;
}[/c]

Could anyone help?

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

### 294 WA

Please give me some input ... Dunno why is error

[c]
#include <stdio.h>

#include <io.h>
#include <fcntl.h>

int main()
{
unsigned long atas,bawah,bilangan;
int n,i,j,hasil,max,jlh;

scanf("%d",&n);
for (jlh=0;jlh<n;jlh++){
scanf("%ld %ld",&bawah,&atas);
max=0;bilangan=0;
for (i=bawah;i<=atas;i++)
{
hasil=0;
for (j=1;j<=i;j++){
if (i%j==0){
hasil++;
}
}
if (hasil>max){
max=hasil;
bilangan=i;
}
}
printf("Between %d and %d, %ld has a maximum of %d divisors.\n",bawah,atas,bilangan,max);
}

return 0;
}
[/c]