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);
        }
    }
}

Comments

Popular posts from this blog

Efficient method to calculate XOR series

Instagram Script to Mass Follow Unfollow in One Click