Facteurs premiers – Bac pratique – Section informatique – 2009

Bac Info 05-12-25

29 0

Sujet (Algo et programmation - Bac 2009)

Soit p et q deux entiers naturels tels que 10 < p < q <100000. On se pr0pose d’enregistrer dans un fichier texte decomp.txt placé sur la racine du lecteur C la décomposition en facteurs premiers de tous les entiers compris entre p et q.

La première ligne du fichier deeomp.txt contiendra le naturel p suivi d’une espace, suivie du naturel q. Chacune des autres lignes contiendra l'entier à décomposer suivi du signe égal suivi de sa décomposition.

Exemple :

Si p=34 et q=36 le fichier Jecomp.txt contiendra des informations suivantes :

34 36

34-2 .17

35=S.7

36=2 .2.3.3

Ecrire un programme en Python qui permet d'afficher à l'écran la décomposition en facteurs premiers de tous les entiers compris entre p ct q ct de remplir le fichier decomp.txt comme décrit précédemment.

Solution Algorithmique

Dans cet algorithme, On va utiliser deux fonctions et une procédure :

- la fonction saisie()

- la fonction facteur_premiers ()

- la procédure remplir_fichier_decomp

Algorithme du programme Principal

Algorithme facteur_premiers
Debut 
     # Saisie de p entre 10 et 100000
     p <- saisie(10, 100000)
     # Saisie de q entre p et 100000 (pour garantir p < q)
     q <- saisie(p, 100000)
     # Appel de la procédure d'écriture du fichier
     remplir_fichier_decomp(p, q)
Fin

Algorithme facteur_premiers

Debut

# Saisie de p entre 10 et 100000

p <- saisie(10, 100000)

# Saisie de q entre p et 100000 (pour garantir p < q)

q <- saisie(p, 100000)

# Appel de la procédure d'écriture du fichier

remplir_fichier_decomp(p, q)

Fin

Déclaration des objets

Objet	Type / Nature
p	entier
q	entier

La fonction saisir

La fonction saisie permet de demander à l’utilisateur un nombre entier n et de vérifier qu’il appartient strictement à l’intervalle : inf < n < sup Elle : 1- affiche une demande de saisie avec les bornes inférieures et supérieures. 2- contrôle la validité de la saisie : tant que l’utilisateur entre une valeur hors de l’intervalle, la fonction redemande un nombre. 3- retourne le nombre correct une fois qu'il est dans la plage exigée.

Fonction saisie(inf:entier, sup:entier): entier    
    Ecrire('donner n tel que ' + inf + '<n<' + sup)
    lire (n)
    # Tant que n n'est pas dans l'intervalle demandé, on redemande
    Tant que (n <= inf) ou (n >= sup) faire
        Ecrire('donner n tel que ' + inf + '<n<' + sup) 
        lire (n)
    Fin tant que
    retourner n # Retourne la valeur correcte
fin

Fonction saisie(inf:entier, sup:entier): entier

Ecrire('donner n tel que ' + inf + '<n<' + sup)

lire (n)

# Tant que n n'est pas dans l'intervalle demandé, on redemande

Tant que (n <= inf) ou (n >= sup) faire

Ecrire('donner n tel que ' + inf + '<n<' + sup)

lire (n)

Fin tant que

retourner n # Retourne la valeur correcte

fin

Déclaration des objets

Objet	Type / Nature
n	entier

La fonction facteur_premiers

Cette fonction permet de décomposer un nombre entier n en ses facteurs premiers et de retourner cette décomposition sous forme de chaîne de caractères.

Elle :

1- recherche les diviseurs premiers de n en commençant par 2.

2- à chaque fois qu’un diviseur i partage n, elle ajoute ce facteur à la chaîne ch (ex : "2.3.3.") et divise n par i pour continuer la décomposition.

3- Si i ne divise pas n, la fonction essaie le diviseur suivant.

4- La boucle continue tant que n n’est pas réduit à 1.

5- Avant de renvoyer le résultat, elle supprime le dernier point inutile.

Fonction facteur_premiers(n:entier):chaine
    i <- 2          # Premier diviseur possible
    ch <- ''        # Chaîne où seront stockés les facteurs

    # Tant que n n'est pas complètement décomposé
    Tant que (n > 1) faire
        # Si i divise n, on ajoute i à la liste des facteurs
        Si (n mod i = 0) alors
            ch <- ch + Convch(i) + '.'   # On ajoute le facteur suivi d'un point
            n <- n / i                # On divise n par i et on continue
        Sinon
            i <- i + 1                # Sinon on teste le diviseur suivant
        Fin si
    Fin tant que
    # On enleve le dernier point inutile avant de retourner le resultat
    retourner Sous_chaine(ch,0,long(ch)-1)
Fin

Fonction facteur_premiers(n:entier):chaine

i <- 2 # Premier diviseur possible

ch <- '' # Chaîne où seront stockés les facteurs

# Tant que n n'est pas complètement décomposé

Tant que (n > 1) faire

# Si i divise n, on ajoute i à la liste des facteurs

Si (n mod i = 0) alors

ch <- ch + Convch(i) + '.' # On ajoute le facteur suivi d'un point

n <- n / i # On divise n par i et on continue

Sinon

i <- i + 1 # Sinon on teste le diviseur suivant

Fin si

Fin tant que

# On enleve le dernier point inutile avant de retourner le resultat

retourner Sous_chaine(ch,0,long(ch)-1)

Fin

Déclaration des objets

Objet	Type / Nature
i	entier
ch	chaîne

La procédure remplir_fichier_decomp

Cette procédure permet de créer un fichier texte contenant la décomposition en facteurs premiers de tous les nombres compris entre p et q (inclus).

Elle effectue les actions suivantes :

1- ouvre un fichier nommé decomp.txt en écriture

2- écrit dans le fichier les bornes p et q

3- pour chaque nombre de l’intervalle [p, q] : elle calcule sa décomposition en facteurs premiers en appelant facteur_premiers(i) et affiche le résultat sur l’écran.

4- ferme le fichier à la fin du traitement.

Procédure remplir_fichier_decomp(p:entier;q:entier):    
    Ouvrir("decomp.txt", f , "w")  # Ouverture du fichier en écriture
    
    Ecrire(p + ' ' + q)
    Ecrire(f,Convch(p) + ' ' + Convch(q) + '\n')

    # Pour chaque nombre entre p et q, calculer sa décomposition
    Pour i de p à q  faire
        Ecrire(Convch(i) + '=' + facteur_premiers(i) + '\n')
        Ecrire(f,Convch(i) + '=' + facteur_premiers(i) + '\n')
    Fin pour
         
    fermer(f)
fin

Procédure remplir_fichier_decomp(p:entier;q:entier):

Ouvrir("decomp.txt", f , "w") # Ouverture du fichier en écriture

Ecrire(p + ' ' + q)

Ecrire(f,Convch(p) + ' ' + Convch(q) + '\n')

# Pour chaque nombre entre p et q, calculer sa décomposition

Pour i de p à q faire

Ecrire(Convch(i) + '=' + facteur_premiers(i) + '\n')

Ecrire(f,Convch(i) + '=' + facteur_premiers(i) + '\n')

Fin pour

fermer(f)

fin

Déclaration des objets

Objet	Type / Nature
f	fichier du nombre.dat
i	entier

Solution en Python

# Fonction pour saisir un nombre n dans l’intervalle (inf, sup)
def saisie(inf, sup):
    # Première saisie
    n = int(input('donner n tel que ' + str(inf) + '<n<' + str(sup)))
    
    # Tant que n n'est pas dans l'intervalle demandé, on redemande
    while (n <= inf) or (n >= sup):
        n = int(input('donner n tel que ' + str(inf) + '<n<' + str(sup)))
    
    return n   # Retourne la valeur correcte


# Fonction pour retourner la décomposition en facteurs premiers d'un entier n
def facteur_premiers(n):
    i = 2          # Premier diviseur possible
    ch = ''        # Chaîne où seront stockés les facteurs

    # Tant que n n'est pas complètement décomposé
    while (n > 1):
        # Si i divise n, on ajoute i à la liste des facteurs
        if (n % i == 0):
            ch = ch + str(i) + '.'   # On ajoute le facteur suivi d'un point
            n = n / i                # On divise n par i et on continue
        else:
            i = i + 1                # Sinon on teste le diviseur suivant
    
    # On enlève le dernier point inutile avant de retourner le résultat
    return ch[0:len(ch) - 1]


# Fonction pour remplir un fichier avec la décomposition en facteurs premiers
# de tous les nombres compris entre p et q
def remplir_fichier_decomp(p, q):
    f = open("decomp.txt", "w")   # Ouverture du fichier en écriture
    
    # Écrire en en-tête les bornes de l’intervalle
    print(str(p) + ' ' + str(q))
    f.write(str(p) + ' ' + str(q) + '\n')

    # Pour chaque nombre entre p et q, calculer sa décomposition
    for i in range(p, q + 1):
        print(str(i) + '=' + facteur_premiers(i) + '\n')
        f.write(str(i) + '=' + facteur_premiers(i) + '\n')
    
    f.close()   # Fermeture du fichier


# ----- Programme principal -----
# Saisie de p entre 10 et 100000
p = saisie(10, 100000)
# Saisie de q entre p et 100000 (pour garantir p < q)
q = saisie(p, 100000)
# Appel de la procédure d'écriture du fichier
remplir_fichier_decomp(p, q)