Lesson: 7
Problem: 294
Title: Divisors
Difficulty Level: 1
Date: Dec 15, 2008
Site: UVA
Simple problem. Your major task is to count the divisor of an integer.
We can count divisors either using prime factorization or using simple loop. Second method is called brute force algorithm, because we counts divisors without any optimization.
As we don’t know how to factorize an integer, so we use 2nd method. lets start.
int Divisors(int n) {
int i, d = 0;
for(i = 1; i<= n; i++) {
if(n%i == 0) {
d++;
}
}
return d;
}
Above function counts the divisors of a integer number. This method is brute force, because we try each number from 1 to N to find divisors. I think you get an idea about brute force.
Now we try to improve our algorithm...
We know 1 and n is always divisor of n, so we can ignore to check those 2 numbers,
int d = 2; // for 1 and n
int i;
for(i = 2; i<= n; i++) {
.....
}
2nd Improvement: if you analyze a bit deep, you will see that no number(say n) has a divisor which is > n/2 but except n. Not clear ? ok, follow me.
let an integer is 10 and it's divisors are: 1 2 5 10.
You can see that there is no divisor from 6 to 9. because 6 > 10/2. i.e no divisor from n/2 + 1 to n - 1. get it ?
int d = 2; // for 1 and n;
int i;
for(i = 2; i<=n/2; i++) {
......
}
3rd Improvement: lets an integer is 20, and its divisors are: 1 2 4 5 10 20
Consider first divisor 1.
20 / 1 = 20, so 20 is an another divisor
Consider 2nd divisor 2
20/ 2 = 10, so 10 is an another divisor
for 3rd one, 4
20/4 = 5, so 5 is an another divisor.
In other word, if we find 1 2 4, we need not to find 20, 10 or 5, get it ?
int d = 0;
for(int i = 1; i*i <= n; i++) {
if(n%i == 0) {
d += 2;
}
}
int k = i - 1;
if(k * k == n) d --;
Here we get 3 important points to note:
1. why i * i <= n
2. why d += 2
3. why k * k = d .....
first 2 cases i leave up to you. Think yourself.
for 3rd case try n = 4 or 9 or n = 16. hope you will get answer.
Now we have to find a number which has maximum divisor between a given range.
int main() {
int max, ans, l, u, n, k;
sacanf("%d",&n); // read the number of case to be read
while(n--) {
scanf("%d%d",&l,&u);
max = Divisor(l);
ans = l;
for(int i = l+1; i<=u; i++) {
k = Divisors(i);
if(k > max) {
max = k;
ans = i;
}
}
printf("Between %d and %d, %d has a maximum of %d divisors.\n",l,u,ans,max);
}
}
Hope i able to make you clear.