Posted:

**Mon Dec 16, 2002 11:05 am**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

Page **2** of **7**

Posted: **Mon Dec 16, 2002 11:05 am**

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

Posted: **Fri Jan 10, 2003 10:44 am**

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.

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.

Posted: **Mon Sep 08, 2003 10:23 am**

[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

readln(n);

for i:=1 to n do begin

readln(x,y);

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]

please help me.

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

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

sum:=sum*(divisor

divisor

end;

end;

scan:=sum;

end;

begin

readln(n);

for i:=1 to n do begin

readln(x,y);

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]

please help me.

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

Posted: **Mon Sep 08, 2003 11:42 am**

Always try borderline cases:
Your program:

Code: Select all

```
1
1 1
```

Code: Select all

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

Posted: **Thu Sep 11, 2003 4:22 pm**

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.

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.

Posted: **Fri Sep 12, 2003 5:55 am**

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

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

Posted: **Fri Sep 12, 2003 1:49 pm**

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.

Posted: **Sun Sep 14, 2003 4:30 pm**

Thanx a lot for the tips, cosmin.ro!!!

Posted: **Sat Oct 04, 2003 3:03 pm**

how should i output my result???

thanks!

thanks!

Posted: **Sat Oct 04, 2003 8:29 pm**

For each range, find the number P which has the largest number of divisors (if several numbers tie for first place, select the lowest)...

Posted: **Sun Oct 05, 2003 8:55 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???

But I have used the prime's method....

So,Is there any aspect i have not notice???

Posted: **Sun Oct 05, 2003 8:21 pm**

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

Please somebody help me...~~

Posted: **Fri Aug 27, 2004 11:45 am**

1 have 1 divisor (after i add this case i got AC)

Posted: **Sat Sep 25, 2004 3:50 am**

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?

[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?

Posted: **Tue Oct 05, 2004 5:32 pm**

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]

[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]