How to Factor an Integer into Primes in C

Introduction

In this lab, you will learn how to factor an integer into its prime factors using a C program. The lab covers the following steps:

Read an integer input from the user.
Implement an algorithm to divide the input number by prime numbers until it is fully factored.
Print the prime factors of the input number.

By the end of this lab, you will have a better understanding of working with integers, prime numbers, and basic programming concepts in C.

Read an Integer

In this step, you will learn how to read an integer input from the user in a C program for prime factorization. We'll create a simple program that prompts the user to enter a number and stores it for further processing.

First, let's create a new C file in the ~/project directory:

cd ~/project
nano prime_factorization.c

Now, add the following code to read an integer:

#include <stdio.h>

int main() {
    int number;

    printf("Enter a positive integer to factorize: ");
    scanf("%d", &number);

    printf("You entered: %d\n", number);

    return 0;
}

Let's break down the code:

#include <stdio.h> includes the standard input/output library
int main() is the main function where program execution begins
printf() is used to display a prompt to the user
scanf() reads the integer input from the user
%d is the format specifier for integers
&number passes the memory address of the number variable

Compile and run the program:

gcc prime_factorization.c -o prime_factorization
./prime_factorization

Example output:

Enter a positive integer to factorize: 24
You entered: 24

Divide by Primes Until Fully Factored

In this step, you will modify the previous program to implement the prime factorization algorithm. We'll update the prime_factorization.c file to divide the input number by prime numbers until it is fully factored.

Open the existing file:

cd ~/project
nano prime_factorization.c

Replace the previous code with the following implementation:

#include <stdio.h>

void factorize(int number) {
    printf("Prime factors of %d: ", number);

    // Start with the smallest prime number
    for (int divisor = 2; divisor <= number; divisor++) {
        while (number % divisor == 0) {
            printf("%d ", divisor);
            number /= divisor;
        }
    }

    printf("\n");
}

int main() {
    int number;

    printf("Enter a positive integer to factorize: ");
    scanf("%d", &number);

    // Check for valid input
    if (number <= 1) {
        printf("Please enter a number greater than 1.\n");
        return 1;
    }

    factorize(number);

    return 0;
}

Let's break down the prime factorization algorithm:

factorize() function handles the prime factorization process
We start with the smallest prime number (2)
The outer for loop tries each potential divisor
The inner while loop divides the number repeatedly by the current divisor
We print each prime factor as we find it
The number is updated by integer division in each iteration

Compile and run the program:

gcc prime_factorization.c -o prime_factorization
./prime_factorization

Example outputs:

Enter a positive integer to factorize: 24
Prime factors of 24: 2 2 2 3

Enter a positive integer to factorize: 100
Prime factors of 100: 2 2 5 5

Print Prime Factors

In this step, you will enhance the prime factorization program to provide more detailed and formatted output of prime factors. We'll modify the existing prime_factorization.c file to improve the presentation of results.

Open the file:

cd ~/project
nano prime_factorization.c

Update the code with an improved factorization function:

#include <stdio.h>

void factorize(int number) {
    int original_number = number;
    int factor_count = 0;

    printf("Prime Factorization of %d:\n", original_number);
    printf("---------------------\n");

    // Start with the smallest prime number
    for (int divisor = 2; divisor <= number; divisor++) {
        int current_factor_count = 0;
        while (number % divisor == 0) {
            number /= divisor;
            current_factor_count++;
            factor_count++;
        }

        // Print factors with their exponents
        if (current_factor_count > 0) {
            printf("%d^%d ", divisor, current_factor_count);
        }
    }

    printf("\n\nTotal number of prime factors: %d\n", factor_count);
}

int main() {
    int number;

    printf("Enter a positive integer to factorize: ");
    scanf("%d", &number);

    // Check for valid input
    if (number <= 1) {
        printf("Please enter a number greater than 1.\n");
        return 1;
    }

    factorize(number);

    return 0;
}

Key improvements in this version:

Added formatting to display prime factors
Shows the exponent of each prime factor
Counts the total number of prime factors
Preserves the original input number for display

Compile and run the program:

gcc prime_factorization.c -o prime_factorization
./prime_factorization

Example outputs:

Enter a positive integer to factorize: 24
Prime Factorization of 24:
---------------------
2^3 3^1
Total number of prime factors: 4

Enter a positive integer to factorize: 100
Prime Factorization of 100:
---------------------
2^2 5^2
Total number of prime factors: 4

Summary

In this lab, you will learn how to read an integer input from the user, implement the prime factorization algorithm, and print the prime factors of the given number. The key steps include reading the integer, dividing the number by prime numbers until it is fully factored, and printing the prime factors.

The program first prompts the user to enter a positive integer, which is then stored in a variable. The prime factorization algorithm is implemented in the factorize() function, where the input number is divided by prime numbers until it is fully factored. The prime factors are then printed to the console.