Efficient way to print factors of a number
Factors of a number n can be defined as the set of numbers which are divisible by n. eg. n=24 factors={1,2,3,4,6,8,12,24}; On native approach this can be done in time complexity O(n), but on efficient approach this can be done in O(sqrt(n));
For n=100;
its factors are 1,2,4,5,10,20,25,50,100;
If noticed carefully, it exists in pair, whose product form the number n;
(1,100),(2,50),(4,25),(5,20),(10,10), we can see an exception for middle element 10, for odd numbers of factors.
Similarly for n=24;
factors: 1,2,3,4,6,8,12, 24
pairs: (1,24),(2,12),(3,8),(4,6)
Further we can notice few more points:
1. If (a,b) is a pair, 1<=a<=sqrt(n)
2. If (a,b) is a pair, b=n/a; as a*b=n
Therefore progmatically,
void Facotrs(int n){
for(int i=1;i<=sqrt(n);i++){
if(n/i=i)//OR i*i==n , for equal divisor element
{
print(i);
}
else{
print(i);
print(n/i);
}
}
}
For n=100;
its factors are 1,2,4,5,10,20,25,50,100;
If noticed carefully, it exists in pair, whose product form the number n;
(1,100),(2,50),(4,25),(5,20),(10,10), we can see an exception for middle element 10, for odd numbers of factors.
Similarly for n=24;
factors: 1,2,3,4,6,8,12, 24
pairs: (1,24),(2,12),(3,8),(4,6)
Further we can notice few more points:
1. If (a,b) is a pair, 1<=a<=sqrt(n)
2. If (a,b) is a pair, b=n/a; as a*b=n
Therefore progmatically,
void Facotrs(int n){
for(int i=1;i<=sqrt(n);i++){
if(n/i=i)//OR i*i==n , for equal divisor element
{
print(i);
}
else{
print(i);
print(n/i);
}
}
}
Comments
Post a Comment