Nombre premier ou composé en utilisant la récursivité

Introduction

Dans ce laboratoire, nous allons apprendre à écrire un programme C qui vérifie si un nombre est un nombre premier ou un nombre composé en utilisant la récursion. Un nombre premier est un nombre qui est divisible seulement par 1 et lui-même, tandis qu'un nombre composé est un nombre qui n'est pas un nombre premier. Nous allons utiliser la récursion pour écrire le programme, qui est une technique pour résoudre des problèmes en les divisant en problèmes plus petits et plus simples.

Obtenir une entrée utilisateur

Nous allons commencer par demander à l'utilisateur d'entrer un nombre entier positif pour vérifier s'il s'agit d'un nombre premier ou d'un nombre composé en utilisant la fonction scanf. Ajoutez le code suivant dans le fichier main.c à l'intérieur de la fonction int main() :

#include <stdio.h>

int main()
{
    int num;
    printf("Entrez un nombre entier positif : ");
    scanf("%d", &num);
    return 0;
}

Écrire la fonction récursive pour vérifier le nombre

Dans cette étape, nous allons écrire la fonction récursive pour vérifier si le nombre est premier ou composé. Cette fonction prend deux arguments - le nombre à vérifier et une variable compteur qui commence par le nombre divisé par 2. Si le compteur atteint 1, la fonction renvoie 1 ce qui indique que le nombre est premier, sinon, la fonction effectue une appel récursif à elle-même avec la variable compteur diminuée. Si à un moment donné, le nombre est divisible par la variable compteur sans reste, la fonction renvoie 0 ce qui indique que le nombre est composé. Ajoutez le code suivant à la fin du fichier main.c :

int isPrime(int n, int c)
{
    if (c == 1) {
        return 1;
    } else {
        if (n % c == 0) {
            return 0;
        } else {
            return isPrime(n, c - 1);
        }
    }
}

Vérification et affichage du résultat

Dans cette étape, nous allons appeler la fonction isPrime pour vérifier si le nombre est premier ou composé. Sur la base du résultat de la fonction, nous allons afficher le message approprié à l'utilisateur. Ajoutez le code suivant à la fin du fichier main.c pour terminer le programme :

int main()
{
    int num, prime;
    printf("Entrez un nombre entier positif : ");
    scanf("%d", &num);
    prime = isPrime(num, num/2);
    if (prime == 1) {
        printf("%d est un nombre premier.\n", num);
    } else {
        printf("%d est un nombre composé.\n", num);
    }
    return 0;
}

Compiler et exécuter le programme

Dans cette étape, nous allons compiler et exécuter le programme. Ouvrez le terminal et accédez au répertoire où se trouve le fichier main.c. Ajoutez la commande suivante dans le terminal pour compiler le programme :

gcc main.c -o main

Ajoutez la commande suivante pour exécuter le programme :

./main

Entrez un nombre entier positif lorsque vous y êtes invité et appuyez sur Entrée. Le programme affichera si le nombre est premier ou composé.

Résumé

Dans ce laboratoire, nous avons appris à écrire un programme C qui vérifie si un nombre est premier ou composé en utilisant la récursivité. Nous avons également appris à utiliser la fonction scanf pour obtenir une entrée utilisateur, écrire une fonction récursive pour vérifier si un nombre est premier ou composé, et afficher le résultat à l'utilisateur. La récursivité est une technique utile pour résoudre des problèmes qui impliquent de les diviser en problèmes plus petits et plus simples.