Décomposer un entier en facteurs premiers en C

Introduction

Dans ce lab, vous allez apprendre à décomposer un entier en ses facteurs premiers à l'aide d'un programme en langage C. Ce lab couvre les étapes suivantes :

1. Lire un entier saisi par l'utilisateur.
2. Implémenter un algorithme pour diviser le nombre saisi par des nombres premiers jusqu'à ce qu'il soit complètement décomposé.
3. Afficher les facteurs premiers du nombre saisi.

À la fin de ce lab, vous aurez une meilleure compréhension de la manipulation des entiers, des nombres premiers et des concepts de base de la programmation en C.

Lire un entier

Dans cette étape, vous allez apprendre à lire un entier saisi par l'utilisateur dans un programme en langage C pour la décomposition en facteurs premiers. Nous allons créer un programme simple qui invite l'utilisateur à saisir un nombre et le stocke pour un traitement ultérieur.

Tout d'abord, créons un nouveau fichier C dans le répertoire ~/project :

cd ~/project
nano prime_factorization.c

Maintenant, ajoutez le code suivant pour lire un entier :

#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;
}

Décortiquons le code :

• #include <stdio.h> inclut la bibliothèque standard d'entrée/sortie
• int main() est la fonction principale où commence l'exécution du programme
• printf() est utilisé pour afficher une invitation à l'utilisateur
• scanf() lit l'entier saisi par l'utilisateur
• %d est le spécificateur de format pour les entiers
• &number passe l'adresse mémoire de la variable number

Compilez et exécutez le programme :

gcc prime_factorization.c -o prime_factorization
./prime_factorization

Exemple de sortie :

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

Diviser par des nombres premiers jusqu'à complète décomposition

Dans cette étape, vous allez modifier le programme précédent pour implémenter l'algorithme de décomposition en facteurs premiers. Nous allons mettre à jour le fichier prime_factorization.c pour diviser le nombre saisi par des nombres premiers jusqu'à ce qu'il soit complètement décomposé.

Ouvrez le fichier existant :

cd ~/project
nano prime_factorization.c

Remplacez le code précédent par l'implémentation suivante :

#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;
}

Décortiquons l'algorithme de décomposition en facteurs premiers :

• La fonction factorize() gère le processus de décomposition en facteurs premiers
• Nous commençons par le plus petit nombre premier (2)
• La boucle for externe essaie chaque diviseur potentiel
• La boucle while interne divise le nombre plusieurs fois par le diviseur actuel
• Nous affichons chaque facteur premier au fur et à mesure qu'il est trouvé
• Le nombre est mis à jour par division entière à chaque itération

Compilez et exécutez le programme :

gcc prime_factorization.c -o prime_factorization
./prime_factorization

Exemples de sorties :

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

Afficher les facteurs premiers

Dans cette étape, vous allez améliorer le programme de décomposition en facteurs premiers pour fournir une sortie plus détaillée et formatée des facteurs premiers. Nous allons modifier le fichier prime_factorization.c existant pour améliorer la présentation des résultats.

Ouvrez le fichier :

cd ~/project
nano prime_factorization.c

Mettez à jour le code avec une fonction de décomposition améliorée :

#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;
}

Principales améliorations de cette version :

• Ajout d'un formatage pour afficher les facteurs premiers
• Affiche l'exposant de chaque facteur premier
• Compte le nombre total de facteurs premiers
• Conserve le nombre d'entrée original pour l'affichage

Compilez et exécutez le programme :

gcc prime_factorization.c -o prime_factorization
./prime_factorization

Exemples de sorties :

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

Résumé

Dans ce lab, vous allez apprendre à lire un entier saisi par l'utilisateur, à implémenter l'algorithme de décomposition en facteurs premiers et à afficher les facteurs premiers du nombre donné. Les étapes clés incluent la lecture de l'entier, la division du nombre par des nombres premiers jusqu'à ce qu'il soit complètement décomposé et l'affichage des facteurs premiers.

Le programme invite d'abord l'utilisateur à saisir un entier positif, qui est ensuite stocké dans une variable. L'algorithme de décomposition en facteurs premiers est implémenté dans la fonction factorize(), où le nombre d'entrée est divisé par des nombres premiers jusqu'à ce qu'il soit complètement décomposé. Les facteurs premiers sont ensuite affichés dans la console.