C Program to Find All Factors of NumberC Program to Display Factors of a Number
In this article, we will learn to write a C program to print all distinct divisors of a number n. Factors of a number are the positive integers that divide the number without leaving a remainder. For example, for n = 10, the factors will be 1, 2, 5 and 10.
Note: This problem is different from finding all prime factors.
A Simple Solution to find all the factors of a number is to iterate all the numbers from 1 to n check if the current number divides n and print the current number.
C Program to Display Factors of a Number
C
// C implementation of Naive // method to print all divisors #include <stdio.h> // Function to print the divisors void printDivisors( int n) { for ( int i = 1; i <= n; i++) if (n % i == 0) printf ( "%d " , i); } // Driver code int main() { printf ( "The divisors of 100 are: " ); printDivisors(100); return 0; } |
The divisors of 100 are: 1 2 4 5 10 20 25 50 100
Complexity Analysis
- Time Complexity: O(n)
- Auxiliary Space: O(1)
We can optimize this time complexity to O(sqrt(n)) by observing that all the divisors are present in pairs. For example if n = 100, then the pairs of divisors are: (1,100), (2,50), (4,25), (5,20), (10,10). Refer to the article Find all factors of a Natural Number for O(sqrt(n)) solution.
But this solution will not print the factors in the sorted order. Please refer to the article Find all divisors of a natural number | Set 2 for an O(sqrt(n)) solution that prints divisors in sorted order.