Les kheys j'ai besoin de votre aide.

J'aimerai faire un programme pour pouvoir décomposer un nombre en facteurs de nombres premiers.

Mais je vois pas comment faire.

J'ai pensé à faire une liste regroupant tous les nombres premiers inférieurs à 100.

Puis ensuite lorsque je rentre un nombre (décomposable avec les nombres premiers inférieurs à 100) la calculette m'affiche les puissances des nombres premiers correspondant sur une liste à coté de la 1ere (pour le coup c'est un peu con car ça m'obligerait de parcourir toute la liste ce qui est une perte de temps. Mais je vois pas comment faire plus simple sans que le programme soit trop long)

Voilà en gros mon projet. Qu'en pensez-vous ? J'ai besoin de votre aide je vois pas qu'est-ce que je dois faire

Une façon simple est de tester chacun des nombres premiers entre 3 et n/2 +1 et voir si il divise n.

Ouais mais au niveau du programme je rédige ça comment ?

Casio ou Texas ?

Ti 82

2 et E(sqrt(n)) si on veut pinailler jusqu'au bout.

Le 30 décembre 2016 à 20:56:26 bluepoint_ a écrit :

Le 30 décembre 2016 à 20:36:56 HighlightReel a écrit :
Une façon simple est de tester chacun des nombres premiers entre 3 et n/2 +1 et voir si il divise n.

3 et sqrt(n) plutôt non ?

Bah non, si on prend 6, la decompo c'est 6=2*3, mais 3 c'est plus que racine de 6

C'est quoi votre histoire de n/2 ?

1. Oui mais au final t'en auras forcément au plus 1 qui est supérieur a sqrt(n) et du coup il est forcément premier

Le 30 décembre 2016 à 21:10:20 GhostlnTheShell a écrit :

1. Oui mais au final t'en auras forcément au plus 1 qui est supérieur a sqrt(n) et du coup il est forcément premier

Je suis pas sur de comprendre qui designe "il" du coup je comprend pas trop la phrase

Je propose :
Une fonction avec une fonction auxiliaire récursive qui prend en argument un nombre premier p et un entier n dont les diviseurs premiers sont plus grands que p et qui renvoie sous une forme ou une autre la décomposition en nombres premiers de n.
Pour l'implémentation, on se contente de chercher le plus petit nombre premier q supérieur ou égal à p qui divise n et on fait un appel récursif aux(q,n/q).
On peut même peaufiner un peu en renvoyant que n est premier si p > sqrt(n)

Voila le programme qu'on a fait en spé en langage Casio :

? -> N
While Frac(N/2) = 0
2►
N/2 -> N
WhileEnd
3 -> D
While N>1 and sqrt(N) ⩾ D
While Frac(N/D) ≠ 0
D+2 -> D
WhileEnd
D►
N/D-> N
WhileEnd

? : saisir
► : afficher
-> : prend la valeur

Je t'en ai fait une sous Python :

def decompo(n) :
x=n
if n==1 :
print(1)
while x!=1 :
for y in range(2,n+1) :
while x%y==0 :
x=x//y
print(y)

% : reste de la division euclidienne
// : quotient de la division euclidienne

Je ne connais pas trop le langage de la TI, mais ça me semble tout à fait faisable sur calculatrice. Après je pense pas que la complexité soit optimale mais bon osef

Le 30 décembre 2016 à 22:16:33 bluepoint_ a écrit :
Je propose aussi (des trucs a priori faisable sans trop de soucis sous TI) :
GNFS
Si n est petit, méthode naïve
Si n est moyen, Rho de Pollard
Et sinon pour gérer le cas éventuel où n est premier qui donne une mauvaise complexité, on peut faire un test genre Miller-Rabin avant

Pour n grand ben y'a le problème du nombre de chiffres significatifs sur la TI donc ça se complique

t'as cru il veut implementer RSA sur sa calculette?