C++/Array Operations Programs/Program

Display Factors of a Number

C++ Program to Display Factors of a Number (5 Methods)

C++Beginner
C++
Try
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int num;
    
    cout << "Enter a number: ";
    cin >> num;
    
    vector<int> factors;
    
    for (int i = 1; i <= num; i++) {
        if (num % i == 0) {
            factors.push_back(i);
        }
    }
    
    cout << "Factors of " << num << " are: ";
    for (int i = 0; i < factors.size(); i++) {
        cout << factors[i] << " ";
    }
    cout << endl;
    
    return 0;
}

Output

Enter a number: 24
Factors of 24 are: 1 2 3 4 6 8 12 24

This program teaches you how to find and display all factors (divisors) of a number in C++. A factor is an integer that divides the number evenly without leaving a remainder. Finding factors is fundamental in number theory, prime factorization, and many mathematical and programming problems.

1. What This Program Does

The program finds all factors of a given number. For example:

  • Input: 24
  • Factors: 1, 2, 3, 4, 6, 8, 12, 24
  • Output: Factors of 24 are: 1 2 3 4 6 8 12 24

A factor is a number that divides the given number exactly (remainder = 0).

Example:

  • Factors of 12: 1, 2, 3, 4, 6, 12
  • Factors of 7: 1, 7 (prime number)
  • Factors of 1: 1 (only one factor)

2. Header Files Used

  1. #include <iostream>

    • Provides cout and cin for input/output operations.

  2. #include <vector>

    • Provides vector container for storing factors dynamically.
    • More flexible than arrays for variable-sized results.

  3. #include <algorithm>

    • Provides algorithms like sort() if needed.
    • Useful for organizing factors.

3. Understanding Factors

Definition:

A factor (divisor) of a number n is an integer d such that n % d == 0.

Properties:

  • Every number has at least two factors: 1 and itself.
  • Factors always come in pairs (except perfect squares).
  • If d is a factor, then n/d is also a factor.

Example (for n = 24):

  • 1 is a factor: 24 % 1 = 0, and 24/1 = 24 is also a factor
  • 2 is a factor: 24 % 2 = 0, and 24/2 = 12 is also a factor
  • 3 is a factor: 24 % 3 = 0, and 24/3 = 8 is also a factor
  • 4 is a factor: 24 % 4 = 0, and 24/4 = 6 is also a factor

4. Declaring Variables

The program declares: int num; vector<int> factors;

  • num stores the number entered by the user.
  • factors is a vector that stores all factors found.

5. Taking Input From the User

The program asks: cout << "Enter a number: "; cin >> num;

The user enters a number, for example: 24

6. Finding Factors Algorithm

The algorithm uses a loop to check all numbers:

for (int i = 1; i <= num; i++) { if (num % i == 0) { factors.push_back(i); } }

How it works:

  • Loop from 1 to num (inclusive).
  • For each i, check if num % i == 0 (i divides num evenly).
  • If yes, add i to the factors vector.

Step-by-step (for num = 24):

i = 1: 24 % 1 = 0 → factors: [1]

i = 2: 24 % 2 = 0 → factors: [1, 2]

i = 3: 24 % 3 = 0 → factors: [1, 2, 3]

i = 4: 24 % 4 = 0 → factors: [1, 2, 3, 4]

i = 5: 24 % 5 = 4 ≠ 0 → skip

i = 6: 24 % 6 = 0 → factors: [1, 2, 3, 4, 6]

i = 7: 24 % 7 = 3 ≠ 0 → skip

i = 8: 24 % 8 = 0 → factors: [1, 2, 3, 4, 6, 8]

...

i = 24: 24 % 24 = 0 → factors: [1, 2, 3, 4, 6, 8, 12, 24]

7. Displaying the Factors

The program displays all factors:

cout << "Factors of " << num << " are: "; for (int i = 0; i < factors.size(); i++) { cout << factors[i] << " "; } cout << endl;

Output: Factors of 24 are: 1 2 3 4 6 8 12 24

8. Optimized Approach (Checking up to sqrt(n))

More Efficient Method:

Instead of checking all numbers from 1 to n, we can check only up to √n:

for (int i = 1; i * i <= num; i++) { if (num % i == 0) { factors.push_back(i); if (i != num / i) { factors.push_back(num / i); } } }

Why it works:

  • Factors come in pairs: if i is a factor, then num/i is also a factor.
  • We only need to check up to √n to find all pairs.
  • For i = num/i (perfect square), add only once.

Example (for num = 24):

  • i = 1: 24 % 1 = 0 → add 1 and 24
  • i = 2: 24 % 2 = 0 → add 2 and 12
  • i = 3: 24 % 3 = 0 → add 3 and 8
  • i = 4: 24 % 4 = 0 → add 4 and 6
  • i = 5: 24 % 5 ≠ 0 → skip
  • Stop when i * i > 24 (i > 4)

Time Complexity:

  • Basic method: O(n)
  • Optimized method: O(√n) - much faster for large numbers

9. Other Methods (Mentioned but not shown in code)

Method 2: Using Arrays

int factors[100]; int count = 0; for (int i = 1; i <= num; i++) { if (num % i == 0) { factors[count++] = i; } }

  • Uses fixed-size array instead of vector.
  • Requires knowing maximum number of factors.

Method 3: Using Two Loops (Separate Small and Large Factors)

vector<int> smallFactors, largeFactors; for (int i = 1; i * i <= num; i++) { if (num % i == 0) { smallFactors.push_back(i); if (i != num / i) { largeFactors.insert(largeFactors.begin(), num / i); } } } // Combine: smallFactors + largeFactors

  • Separates small and large factors.
  • Can be useful for specific ordering needs.

Method 4: Recursive Approach

void findFactors(int num, int i, vector<int>& factors) { if (i > num) return; if (num % i == 0) { factors.push_back(i); } findFactors(num, i + 1, factors); }

  • Recursive implementation.
  • Less efficient due to function call overhead.

10. When to Use Each Method

  • Basic Loop (1 to n): Best for learning - simple and clear.

  • Optimized (up to √n): Best for efficiency - recommended for large numbers.

  • Vectors: Best for flexibility - dynamic size, easy to use.

  • Arrays: Good when maximum size is known - fixed memory.

Best Practice: Use optimized method with vectors for most cases.

11. Important Considerations

Edge Cases:

  • num = 1: Only factor is 1
  • num = 0: All numbers are factors (or undefined, depending on definition)
  • Negative numbers: Typically work with absolute value

Perfect Squares:

  • For perfect squares (e.g., 16 = 4²), factor 4 appears only once
  • Check: if (i != num / i) before adding num/i

Large Numbers:

  • For very large numbers, use optimized method (O(√n))
  • Consider using long long for large inputs

Sorting Factors:

  • Factors from optimized method may not be in order
  • Use sort(factors.begin(), factors.end()) if needed

12. Common Use Cases

Number Theory:

  • Prime factorization
  • Finding divisors
  • Mathematical research

Programming Problems:

  • Competitive programming
  • Coding interviews
  • Algorithm practice

Real-World Applications:

  • Cryptography
  • Number system conversions
  • Mathematical computations

13. return 0;

This ends the program successfully.

Summary

  • Factors are numbers that divide evenly (remainder = 0).
  • Basic method checks all numbers from 1 to n: O(n) time.
  • Optimized method checks only up to √n: O(√n) time - much faster.
  • Factors come in pairs: if i is a factor, num/i is also a factor.
  • Use vectors for dynamic storage, arrays for fixed size.
  • Understanding factors is essential for number theory and algorithms.
  • Multiple methods exist: basic loop, optimized, arrays, vectors, recursion.
  • Choose method based on needs: learning vs. efficiency vs. code organization.

This program is fundamental for beginners learning number theory, understanding loops and conditionals, and preparing for prime factorization, GCD/LCM calculations, and more advanced number theory problems in C++ programs.

Previous
Matrix Multiplication