samedi 6 juin 2020

Ensemble des diviseurs d'un entier naturel

Prétexte pour construire à la volée une pile LIFO en C.

Introduction

Dans tout cet article il ne sera question que d'entiers naturels non nuls. Leur ensemble est noté ℕ*. ℕ*={1, 2, 3, 4, ...}

Définition

Étant donné un entier naturel non nul $n$, on dit que l'entier naturel $d$ divise $n$ s'il existe un entier naturel $p$ tel que $n=dp$. On dit aussi que $d$ est un diviseur de $n$.

On souhaite écrire l'ensemble $D(n)$ des diviseurs de $n$ ($n\in$ ℕ*). On voudrait de plus que cette écriture soit ordonnée dans l'ordre des naturels.

Exemples :

$D(12) = \{1, 2, 3, 4, 6, 12\}$

$D(25)=\{1, 5, 25\}$

Algorithme naif

Sachant que tous les diviseurs de $n$ appartiennent à $[1, n]$ on peut tester tous les entiers de cet intervalle, c'est à dire calculer le reste de la division entière de $n$ par chacun d'eux et regarder si elle est nulle. (n \% d == 0 en C).

Cet algorithme donne bien l'ensemble ordonné des diviseurs de $n$ mais au prix de $n$ calculs de restes et autant de comparaisons.

Algorithme plus rapide

L'idée

Les diviseurs vont par paires. Exemples :

$$D(12)=\{1, 12\}\cup\{2,6\}\cup\{3,4\}$$

$$D(25)=\{1,25]\cup\{5\}$$

Dans le dernier exemple 5 est appareillé avec lui même.

Partition de $D(n)$

Faisons une partition de $D(n)$ en :

$$D_1(n)=\{p\in D(n)~|~ p\lt \sqrt{n}\}$$

$$D_2(n)=\{q\in D(n)~|~q\gt \sqrt{n}\}$$

$$D_0=\{m\inD(n)~|~m=\sqrt{n}\}$$ ce dernier pouvant être vide.

Remarque

Ici on observe que si $p$ divise $n$ et $p\gt \sqrt{n}$ alors $\existsq\le \sqrt{n}, n=pq.$ (il suffit de multiplier les deux membres de $p\gt \sqrt{n}$ par $\dfrac{q}{\sqrt{n}}$ qui est positif).

Alors, d'après la remarque ci-dessus, tout élément de $D_2(n)$ peur être obtenu comme quotient de $n$ par un élément de $D_1(n).$

Il devient moins onéreux en termes de calcul de tester tous les entiers $p$ positifs inférieurs à $\sqrt{n}$ et de réserver le quotient $q=\dfrac{n}{p}$ qui est aussi un diviseur de $n$.

On utilise une pile LIFO pour stocker ces autres diviseurs.

Remarque : On évitera d'empiler $\sqrt{n}$ dans le cas où celui-ci est un entier qui divise $n$, afin de ne pas afficher un doublon.

Voici le source du programme divisors.c

 1 /*
 2 :w | !gcc \% -o .\%< -lm
 3 :w | !gcc \% -o .\%< -lm && ./.\%<
 4 */
 5 
 6 #include <stdio.h>
 7 #include <string.h>
 8 #include <stdlib.h>
 9 #include <math.h>
10 
11 // unsigned int
12 typedef unsigned long int ulong;
13 
14 // stack used to store divisors greater than sqrt(n)
15 typedef struct stack {
16    ulong u;
17    struct stack *next;
18 } *stkptr; // stack pointer type
19 
20 /**
21 divisors(u) prints divisors of u 
22 u ulong
23 */
24 void divisors(ulong);
25 
26 /**
27 getulong(&u) reads an unsigned int from stdin
28 u ulong
29 returns 1 if succes and 0 else
30 */
31 int getulong(ulong *);
32 
33 int main()
34 {
35    printf("Integer factorization∖n");
36    ulong n;
37    while(getulong(&n))
38       divisors(n);
39    puts("End");
40 }
41 
42 void divisors(ulong u)
43 {
44    stkptr top = NULL; // stack pointer 
45    ulong d2; // other divisor
46    ulong sqrtu = (ulong)sqrt((double)u);
47 
48    printf("D(\%lu) = {", u);
49    for(ulong d1 = 1; d1 <= sqrtu; d1++) { // low divisors
50       if(u \% d1 == 0) {
51          d2 = u / d1; // d1*d2 = u
52          printf("\%lu, ", d1);
53          // push d2
54          if(d2 > d1) {
55             stkptr node = (stkptr )malloc(sizeof(stkptr));
56             node->u = d2;
57             node->next = top;
58             top = node;
59          }
60       }
61    }
62    // pull remaining divisors
63    while(top->next != NULL) {
64       printf("\%lu, ", top->u);
65       stkptr freed = top;
66       top = top->next;
67       free(freed);
68    }
69    printf("\%lu}∖n", top->u); // the last must be u
70    free(top);
71 }
72 
73 int getulong(ulong *u)
74 {
75    char *line = NULL;
76    size_t len = 0;
77    int result;
78    printf("unsigned int : ");
79    getline(&line, &len, stdin);
80    result = (sscanf(line, "\%lu", u) == 1);
81    free(line);
82    return result;
83 }
84 

Commentaires

Ligne 12

Le type ulong peut être adapté, par exemple unsigned long long int.

Ligne 15

La structure stack est un nœud de pile LIFO. Chaque nœud pointe sur le suivant, le dernier étant NULL.

Ligne 18

stkptr est un pointeur sur une structure stack.

Lignes 33 à 40

Le programme. Il demande un entier non signé et affiche l'ensemble de ses diviseurs. Le programme s'arrête lorsqu'on ne saisit aucun entier (on tape Enter seul).

Lignes 42 à 70

La fonction qui recherche et affiche les diviseurs d'un entier. Ici la notation est u, pour ulong et non $n$.

Ligne 44

Initialisation de la pile.

Ligne 46

Calcul de la racine carrée de u.

Attention : il faut inclure math.h et compiler avec l'option -lm. Voir les lignes 2 et 3. Pour comprendre comment j'utilise ces lignes dans vim voyez mon article vim.

Lignes 49 à 61

Calcul des diviseurs inférieurs à $\sqrt{u}$. Chaque diviseur d1 est affiché et le quotient de u par d1, s'il est différent de d1 est empilé.

Lignes 55 à 58

C'est ici qu'on réserve les diviseurs associés. On crée un nouveau nœud node qui contient le diviseur à réserver et qui pointe sur le haut de la pile, puis on le fait devenir le haut de la pile.

Lignes 63 à 70

Lorsque les calculs précédents sont terminés, on dépile un à un les diviseurs qui ont été empilés en les affichant. On libère alors la mémoire allouée au nœud qui vient d'être dépilé et on abaisse le haut de la pile.

Remarque : la pile n'est jamais vide, elle contient au moins u.

Lignes 73 à 83

La fonction getulong est la fonction de saisie.

J'ai choisi d'utiliser la fonction getline (voir man 3 getline) qui semble avoir été ajoutée pour ça, d'abord par GNU puis standardisée.

Voir man 3 gets et man 3 fgets.

Voir aussi fgets vs. getline in C et Why is the fgets function deprecated?.

Habituellement j'utilisais fgets et cette fois j'ai voulu essayer getline.

Comparaison des deux algorithmes

La différence entre l'algorithme naïf et le second peut être significative.

Pour le nombre 1234567890 le premier met 9,478417 secondes, alors que pour le second il ne faut que 0,001199 secondes.

Carrément grognon

Je pouvais coder la pile de façon plus classique en définissant les fonctions pop et push (fichier joint ulstack.c).

  1 /*
  2 :w | !gcc \% -o .\%< -lm
  3 :w | !gcc \% -o .\%< -lm && ./.\%<
  4 */
  5 
  6 #include <stdio.h>
  7 #include <stdlib.h>
  8 #include <string.h>
  9 #include <limits.h>
 10 #include <math.h>
 11 
 12 typedef unsigned long int ulong;
 13 
 14 #define Nan ULONG_MAX; // not a number
 15 
 16 typedef struct ulstack {
 17    ulong u;
 18    struct ulstack *next;
 19 } *ulstkptr; // must be initilized to NULL
 20 
 21 /*
 22 ulstk_push(stk, u) push u on the top of the stack *stk
 23 *stk is an ulstkptr
 24 u is an ulong
 25 returns void
 26 */
 27 void ulstk_push(ulstkptr *, const ulong);
 28 
 29 /*
 30 ulstk_pop(*stk)
 31 *stk is an ulstkptr
 32 returns top value if the stack is not empty
 33 returns Nan if the stack is empty
 34 */
 35 ulong ulstk_pop(ulstkptr *);
 36 
 37 /**
 38 divisors(u) prints divisors of u 
 39 u ulong
 40 */
 41 
 42 void divisors(ulong);
 43 /**
 44 getulong(&u) reads an unsigned int from stdin
 45 u ulong
 46 returns 1 if succes and 0 else
 47 */
 48 int getulong(ulong *);
 49 
 50 int main(int argc, char *argv[])
 51 {
 52 
 53    printf("Integer factorization∖n");
 54    ulong n;
 55    while(getulong(&n))
 56       divisors(n);
 57    puts("End");
 58 }
 59 
 60 
 61 void ulstk_push(ulstkptr *top, const ulong u)
 62 {
 63    ulstkptr newtop = (ulstkptr)malloc(sizeof(struct ulstack));
 64    if(newtop == NULL) {
 65       puts("push failed");
 66       exit(1);
 67    }
 68    newtop->u = u;
 69    newtop->next = *top;
 70    *top = newtop;
 71 }
 72 
 73 ulong ulstk_pop(ulstkptr *stk)
 74 {
 75    if(*stk == NULL) return Nan; // empty stack
 76    ulong u = (*stk)->u; // value of the top
 77    ulstkptr top = *stk; // to be freed
 78    *stk = (*stk)->next; // new top pointer
 79    free(top); // free the old top
 80    return u;
 81 }
 82 
 83 void divisors(ulong u)
 84 {
 85    ulstkptr top = NULL; // stack pointer 
 86    ulong d2; // other divisor
 87    ulong sqrtu = (ulong)sqrt((double)u);
 88 
 89    printf("D(\%lu) = {", u);
 90    for(ulong d1 = 1; d1 <= sqrtu; d1++) { // low divisors
 91       if(u \% d1 == 0) {
 92          d2 = u / d1; // d1*d2 = u
 93          printf("\%lu, ", d1);
 94          // push d2
 95          if(d1 < d2)
 96             ulstk_push(&top, d2);
 97       }
 98    }
 99    // pull remaining divisors
100    while(top->next != NULL) {
101       printf("\%lu, ", top->u);
102       ulstk_pop(&top);
103    }
104    printf("\%lu}∖n", top->u); // the last must be u
105    free(top);
106 }
107 
108 int getulong(ulong *u)
109 {
110    char *line = NULL;
111    size_t len = 0;
112    int result;
113    printf("unsigned int : ");
114    getline(&line, &len, stdin);
115    result = (sscanf(line, "\%lu", u) == 1);
116    free(line);
117    return result;
118 }
119 

Est-ce bien utile ? On n'utilise ces fonctions qu'une seule fois.


Réalisé avec Qlam - LGPL