Print All Factors of N

Problem Statement

Given a positive integer n, print all of its factors in ascending order.

A factor of a number is an integer that divides the number evenly (without leaving a remainder).

Examples

Example 1:

Input: n = 6
Output: 1, 2, 3, 6

Explanation: The factors of 6 are:
1*6 = 6
2*3 = 6
Hence, the factors are [1, 2, 3, 6].

Example 2:

Input: n = 12
Output: 1, 2, 3, 4, 6, 12

Explanation: All integers that divide 12 evenly are 1, 2, 3, 4, 6, 12.

Example 3:

Input: n = 1
Output: 1

Explanation:
1 is a factor of itself.

Constraints:

• 1 ≤ n ≤ 10^9

Different Approaches

1️⃣ Brute Force Approach

Intuition:

The most basic solution we can do is to traverse from 1 to n and keep if that number divides the n with remainder 0, by using modulus operator. If so print that number.

Approach:

1. Loop i from 1 to n.
2. If n % i == 0, print i.

Code:

#include <iostream>
using namespace std;

int main() {
    long long n;
    cin >> n;

    for (long long i = 1; i <= n; i++) {
        if (n % i == 0) {
            cout << i << " ";
        }
    }
    return 0;
}

Complexity Analysis:

• Time Complexity: O(n)
  • Loop runs n times
• Space Complexity: O(1)
  • Only a few variables used

2️⃣ Square Root (Optimized Approach)

Intuition:

let f1 and f2 be the factors of the n, then we can represent
f1 * f2 = n
If we discovered f1 then with this we can discover the second factor as:
f2 = n / f1

If i is a factor of n, then n / i is also a factor.

For example, for n = 36

1 * 36
2 * 18
3 * 12
4 * 9
6 * 6

After i > square root of n, the factors start repeating.

So, we only need to loop till square root of n, and print both i and n / i.

Algorithm:

1. Loop i from 1 to square root of n.
2. If n % i == 0:
   1. Print i
   2. If i != n / i, print n / i as well.

Code:

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    long long n;
    cin >> n;

    cout << "Factors of " << n << " are: ";

    for (long long i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            cout << i << " ";
            if (i != n / i)
                cout << n / i << " ";
        }
    }

    return 0;
}

Complexity Analysis:

• Time Complexity: O(Sqrt(n))
• Space Complexity: O(1)