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

pc5971
New poster
Posts: 34
Joined: Mon Aug 05, 2002 11:24 am
Contact:

Post by 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
Learning poster
Posts: 65
Joined: Sun Jun 02, 2002 8:41 pm
Location: BANGLADESH
Contact:

Post by 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. :-?

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

294 - Divisors

Post by 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
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by 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
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.

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

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

Post by 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
Experienced poster
Posts: 136
Joined: Tue Apr 01, 2003 6:59 am
Location: Jakarta, Indonesia

Post by Joseph Kurniawan »

Thanx a lot for the tips, cosmin.ro!!! :P :P
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....

Post by nonstop »

how should i output my result???
thanks!

UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by 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
New poster
Posts: 14
Joined: Fri Oct 03, 2003 5:13 am

...

Post by 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
New poster
Posts: 14
Joined: Fri Oct 03, 2003 5:13 am

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

Post by 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.....
:cry:
Please somebody help me...~~ :cry:

Arm.Turbo
New poster
Posts: 21
Joined: Wed Aug 11, 2004 1:20 pm

Post by Arm.Turbo »

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.

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

294 WA

Post by 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]

Post Reply

Return to “Volume 2 (200-299)”