Prime Factorization Program in C++

Introduction

Prime factorization is the process of determining the prime numbers that multiply together to give a particular original number. Prime numbers are integers greater than 1 that are divisible only by 1 and themselves. This is an important concept in number theory and has numerous applications in cryptography, coding theory, and other branches of mathematics.

Objective

The objective of this program is to find and print all the prime factors of a given integer. The program will accept an integer from the user and display its prime factors in ascending order.

Code

#include 
using namespace std;

// Function to find and print prime factors of a number
void primeFactors(int n) {
    // Divide by 2 to check for even factors
    while (n % 2 == 0) {
        cout << 2 << " ";
        n = n / 2;
    }

    // n must be odd at this point. Start checking from 3 and increment by 2
    for (int i = 3; i * i <= n; i += 2) {
        // While i divides n, print i and divide n by i
        while (n % i == 0) {
            cout << i << " "; n = n / i; } } // If n is a prime number greater than 2 if (n > 2) {
        cout << n << " ";
    }
}

int main() {
    int num;

    // User input
    cout << "Enter a number to find its prime factors: "; cin >> num;

    cout << "Prime factors of " << num << " are: ";
    primeFactors(num);

    return 0;
}

Explanation

This program starts by prompting the user to input a number. The function primeFactors(int n) performs the prime factorization by checking for divisibility of the number with prime numbers starting from 2.

Here’s how the code works:

• The program first checks if the number is divisible by 2 (the smallest prime number) and repeatedly divides it by 2 until it’s no longer divisible.
• Then, it checks for divisibility by odd numbers starting from 3. This is because all even numbers greater than 2 are not prime.
• It continues this process until the square root of the number, as any factor larger than the square root would already have a corresponding smaller factor.
• If the remaining number after all divisions is greater than 2, that number itself is a prime factor, and it is printed as the last prime factor.

How to Run the Program

To run this program, follow these steps:

1. Copy the code provided above into a C++ editor or IDE (such as Visual Studio, Code::Blocks, or any other C++ compiler).
2. Save the file with a .cpp extension (e.g., prime_factorization.cpp).
3. Compile the program by clicking the “Build” or “Compile” button in your editor, or use a terminal/command prompt to compile with the command: g++ -o prime_factorization prime_factorization.cpp.
4. Run the program by executing the generated executable file (e.g., ./prime_factorization in the terminal or command prompt).
5. Enter an integer when prompted, and the program will output the prime factors of the number.