## 294 - Divisors

Moderator: Board moderators

Ghust_omega
Experienced poster
Posts: 115
Joined: Tue Apr 06, 2004 7:04 pm
Location: Venezuela
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 !! jhonny_yang
New poster
Posts: 22
Joined: Fri Jan 17, 2003 8:24 am

### Re: Cul de sac.

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.

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

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={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
You got division by zero in this line while(j%primes[pm]==0)

CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 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
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
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
infact you do not even need to find primes at all.
Would you please explain in more detail?

alu_mathics
Learning poster
Posts: 55
Joined: Sat Jan 24, 2004 9:30 pm
Location: Chittagong
Contact:
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
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!!!

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:
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
Thank you very much mf. I got AC.

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

### Divisors-294 WA

Code: Select all

``````program divisor294;
var     n,i,l,k,temp,m,o,p,max,kand,a,j,t:longword;
begin
for j:=1 to k do
begin
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.``````