Bonjour,  
 
Je réfléchis à la conception d'un petit programme d'arithmétique en langage C qui serait en mesure d'obtenir certaines informations liées à la décomposition d'un entier en produit d'irréductibles : somme des diviseurs, fonction d'Euler, que-sais-je-encore... et ce pour un grand nombre d'entiers (disons ceux inférieurs à 10 millons...)
 
Ce qui me turlupine c'est le fait que pour stocker la liste des facteurs premiers d'un entier et les valuations associées au moyen de tableaux d'entier (resp de char), il faut d'abord connaître une borne supérieure du nombre des tels facteurs.
 
Bon en l'occurrence, comme tout entier < 2*3*5*...*17*19 en a moins de 8, c'est un peu un faux problème. Mais dans un autre anneau factoriel, on risquerait de ne pas avoir de ruse de ce type eg un anneau de polynômes sur un corps fini...)
 
Au pire, je serais en mesure de déterminer cette borne supérieure au sein du programme, mais ensuite impossible de définir une structure contenant un tableau de cette taille (qui est une variable !
 
Y'aurait-il moyen de faire un truc comme ça quand même : déclarer une structure de taille variable (je pense pas, car comment ferait malloc ?) et sinon vous régleriez ça par une liste chaînée ?
 
Dans l'attente de votre expertise,  
 
Ced'
 
 
EDIT : euh en fait il suffirait de mettre dans ma structure décomposition un char "nombre de facteurs" et un pointeur vers le premier élément d'un tableau[nombre de facteurs] de struct diviseur_premier
 
avec

 
 
 
Bon je laisse le sujet quand même.

Pourquoi refaire ce que fait déjà très bien Mathematica, Matlab, Maple, Maxima, etc. ?
 
Pourquoi choisir le langage C, alors qu'il existe beaucoup d'autres langages qui sont beaucoup plus facile à programmer pour cela ?
Par exemple, rien que le C++ offre divers structures variables beaucoup plus pratiques que celles du C.
 
Ou bien, pourquoi ne pas utiliser une bibliothèque tiers qui travaille sur des grands nombres, par exemple, bigint, gmp, bign, etc. ?
 
Pourquoi est-ce que je pose ces questions ?
Parce que j'ai moi-même fait un petit programme travaillant sur des grands nombres. J'avais utilisé un tableau à une dimension, que je dimensionnais avec malloc(), que je redimensionnais avec realloc() selon les besoins. Cela marchait. Mais au final, j'ai utilisé beaucoup de temps pour pas grand chose.

Les solutions suivantes me viennent à l'esprit :

• Tu comptes tout d'abord le nombre de facteur, tu alloues un tableau de cette taille et tu parcours à nouveau les facteurs premiers en les stockant ;
• Tu utilises une liste chaînée ;
• Tu agrandis la taille du tableau au fur et à mesure (par exemple en utilisant realloc).
• Tu alloues un tableau trop grand que tu n'utiliseras pas en totalité (ou redimensionnera une unique fois à la fin)

@billgatesanonym
 
Merci pour tes remarques. D'abord, j'ai pensé à un programme de ce type pour www.projecteuler.net, où il y a souvent besoin de factoriser des entiers.
 
Je suis assez d'accord avec l'idée que tu décris dans une perspective 'ingénieur'. Mais ce n'est pas mon approche : je cherche simplement à me former à la programmation en prenant une approche minimaliste, et je compte pas spécialement faire fortune grâce à mon programme pour calculer la fonction d'Euler   ... Je n'ignore pas que des fonctions ce genre sont déjà implémentées, et d'une manière moins naïve que ce que je fais. Cela dit, utiliser des librairies C++ surpuissantes pour traiter des problèmes aussi basiques, je trouve pas ça très élégant...
 
J'ai déjà essayé le langage python, j'ai bien aimé ça, mais ça tue tout l'intérêt pédagogique : tu lui demandes la factorielle de 100, et il te retourne trois lignes de chiffres, bonjour les boîtes noires pour apprendre !  (et par ailleurs, je trouve que le C est vraiment cool   )
 
Si t'as des problèmes de programmation (ou des suggestions de langage) qui soient intéressants, formateurs et novateurs, (et à mon niveau de compétence (pas très haut, donc...)) , je suis preneur ! (je vais peut-être pas suivre tes conseils pour le langage, en revanche...)
 
--
Ced'
 

Bonjour,
Ton approche me semble assez bonne, Mais IMHO, il y a qque chose d'inutile dans ta manière d'attaquer le problème:

Je pense que dans de nombreux cas, tu n'as pas besoin de connaitre la valeur du nb premier, mais juste son indice et la valuation.
Et quand tu as besoin de la valeur, tu utilises le tableau des nombres premiers avec le bon indice.

Je suppose que dans le programme tu associes à un entier une structure décomposition, composée d'au moins deux champs:
un entier, le nombre de facteurs premiers
un pointeur sur struct diviseur_premier qu'on fera pointer sur un tableau de nombre de facteurs premiers de  struct diviseur_premier, tableau alloué dynamiquement.

A+,

Pourquoi préfères-tu utiliser l'indice qu'un pointeur vers cette case du tableau ? Pour une question de stockage en mémoire ? Quitte à ...taquiner des mouches, un pointeur prend plus de place, mais il n'y a pas d'addition à faire pour aller à l'endroit en question contrairement à array[index] = *(array + index), donc c'est plus rapide, non ?  

Oui, c'est pour ça que j'utilise un pointeur : je ne comprends pas ta remarque...  

Oui, c'est mon idée.

Parce que comme je l'ai dit, si tu tapes pas trop haut dans les nombres de ton programme, ca tiendra dans un char plutôt que dans un int, et tu va gagner de la place.

Peut être, mais stocker un nombre ici à un sens intrinsèque: la valeur n (ou n-1 selon ses choix) représente le n-ième nombre premier. On perd cette information en utilisant des pointeurs.
Un exemple: Si je veux déterminer si un nombre a beaucoup de trous ou non dans sa décomposition, tu vas considérer la valeur max de indice_premier dans ta décomposition (et comme si c'est bien fait, c'est ordonné, c'est immédiat) - le nb d'éléments de ta décomposition, c'est très simple à calculer ici, ça me semble bien moins simple avec des pointeurs.
A+,