294 - Divisors

[pc5971]

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]

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]

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

[little joey]

Always try borderline cases:

Code: Select all

1
1 1

Your program:

Code: Select all

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

[epsilon0]

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.

[Joseph Kurniawan]

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

[Cosmin.ro]

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]

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

[nonstop]

how should i output my result???
thanks!

[UFP2161]

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]

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]

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

[Arm.Turbo]

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

[Ndiyaa ndako]

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]

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]