Forum de mathématiques - Bibm@th.net

okbob852

Membre

Inscription : 12-07-2025

Messages : 38

factorisation avec Python

bonjour
je voudrais savoir en factorisant un nombre issue de la multiplication de 2 nombres premiers  et ça avec le programme python ,combien d’opérations faut il pour arriver au résultat (le 1er nombre premiers)
prenons comme exemple le nombres 74747503
seulement pour comparer
merci

Pierre Lescanne

Invité

Re : factorisation avec Python

La question est intéressante et fondamentale, mais elle n'a pas de réponse facile.

Ce problème, très difficile, est à la base de nombreux systèmes de cryptologie, dont le système RSA, très utilisé sur Internet.  La réponse est « beaucoup », beaucoup plus que ce que nos ordinateurs classiques peuvent faire. 

Donc la difficulté de cette factorisation protège nos clés de chiffrement, avent l’arrivée des ordinateurs quantiques. Mais ces ordinateurs  ne se programment pas en Python.

Ai-je répondu à la question ?

LEG

Membre

Inscription : 19-09-2012

Messages : 790

Re : factorisation avec Python

Comme dit précédemment  il n'y a pas de réponse simple... car soit on s'amuse à chercher le premier facteur de ce produit P*q de deux facteurs premiers ...  , en utilisant tous les nombres premiers p-1, p-2 ....p-n < à racine carré du produit... soit on va sur un site comme (ex : https://www.alpertron.com.ar) qui utilise des moyens sophistiqués, probabilistes ...etc , et qui te donne une réponse  en  moins d'une seconde ou plus... en fonction de la valeur du produit...

Bon amusement...

okbob852

Membre

Inscription : 12-07-2025

Messages : 38

Re : factorisation avec Python

Et c’est ce qu’ il a dit cheikh Google
Nombre d'opérations avec Python:
•    [Algorithme naïf (division successive): Ce type d'algorithme teste tous les diviseurs possibles jusqu'à la racine carrée du nombre. Pour un nombre de 7 chiffres (par exemple 1 000 000), cela pourrait impliquer jusqu'à 1000 divisions successives.
•    Pour un nombre de 7 chiffres, la complexité peut être relativement faible si le nombre a des petits facteurs premiers. Cependant, si le nombre est le produit de deux grands nombres premiers, la factorisation peut être très longue. ]

avec le nombre que j'ai donné comme exemple ,en python je cherche le nombre exacte d'operations pour le comparer avec mes resultat, si je suis en plus ou en moin
et si ce probleme est posé dans des examen à des eleves en secondaire ou universtaire en utilisant python meme si le nombres est de 5 chiffres est ce qu'il seras à leur portée

Dernière modification par okbob852 (13-07-2025 09:53:54)

Ernst

Membre

Inscription : 30-01-2024

Messages : 339

Re : factorisation avec Python

Bonjour,

On peut toujours écrire un programme Python qui fait le job, en utilisant une recherche un poil plus rapide que tester tous les nombres possibles :
- on teste 2 et 3
- puis tous les multiples de 6 plus ou moin 1 (donc 5, 7, 11, 13, 17, 19, etc.)
- et s'arrêter à la racine carrée

import math

def factoriser(n):
    if n < 2:
        print("Veuillez entrer un entier supérieur ou égal à 2.")
        return

    original_n = n
    facteurs = []
    tentatives = 0

    # Diviser par 2
    while n % 2 == 0:
        facteurs.append(2)
        n //= 2
        tentatives += 1

    # Diviser par 3
    while n % 3 == 0:
        facteurs.append(3)
        n //= 3
        tentatives += 1

    # Teste les diviseurs de la forme 6k ± 1
    i = 5
    max_diviseur = math.isqrt(n) + 1
    while i <= max_diviseur:
        for d in [i, i + 2]:  # i = 6k - 1 et i+2 = 6k + 1
            while n % d == 0:
                facteurs.append(d)
                n //= d
                tentatives += 1
                max_diviseur = math.isqrt(n) + 1  # Mise à jour après division

            tentatives += 1  # On a tenté la division même si elle a échoué

        i += 6

    # Si il reste un nombre premier
    if n > 1:
        facteurs.append(n)
        tentatives += 1

    print(f"Facteurs de {original_n} : {facteurs}")
    print(f"Nombre de tentatives de division : {tentatives}")

# Exemple d'exécution
if __name__ == "__main__":
    try:
        nombre = int(input("Entrez un entier à factoriser : "))
        factoriser(nombre)
    except ValueError:
        print("Veuillez entrer un entier valide.")
 

La réponse est pratiquement instantanée.

Facteurs de 74747503 : [8447, 8849]
Nombre de tentatives de division : 2818

okbob852

Membre

Inscription : 12-07-2025

Messages : 38

Re : factorisation avec Python

MERCI pour la réponse
le nombre d’opérations(division) qui m(intéresse le plus
pour mes résultat le nombre est 1408 c'est a dire la moitié ou presque de 2418
pour être crédible
je vous donne 3 nombres en mémé temps le nombre d’opérations
  24960007 ***les 2 nombres premiers apprissent à l 832eme opération
14705773***** ils apparaissent à la 652eme opération
2428216771*****ils apparaissent à la 8057eme operation
normalement en raison de votre réponse vos résultat serons doublé
832*2/**1664
652*2/**1304
8057*2/16114
à vitrifier ,publiez le résultat python de l'un d'eux
merci

Ernst

Membre

Inscription : 30-01-2024

Messages : 339

Re : factorisation avec Python

Bonjour,

Code légèrement amélioré et compacté :

import math, time

def factoriser(n):
    if n < 2:
        print("Entier ≥ 2 requis."); return
    orig, f, t = n, [], 0
    deb = time.time()

    while n % 2 == 0: f.append(2); n //= 2; t += 1
    while n % 3 == 0: f.append(3); n //= 3; t += 1

    i = 5; max_d = math.isqrt(n)
    while i <= max_d:
        while n % i == 0:
            f.append(i); n //= i; t += 1
            max_d = math.isqrt(n)
        t += 1
        d = i + 2
        while n % d == 0:
            f.append(d); n //= d; t += 1
            max_d = math.isqrt(n)
        t += 1
        i += 6

    if n > 1: f.append(n); t += 1
    fin = time.time()

    print(f"Facteurs de {orig} : {f}")
    print(f"Divisions : {t} | Temps : {fin - deb:.6f} s")

if __name__ == "__main__":
    try: factoriser(int(input("Entier à factoriser : ")))
    except: print("Entrée invalide.")
 

Pour des nombres allant jusqu'à une quinzaine de chiffres, le temps d'obtention du résultat va être de l'ordre de la seconde sur une machine récente.

Entier à factoriser : 24960007
Facteurs de 24960007 : [4993, 4999]
Divisions : 1666 | Temps : 0.000000 s

Entier à factoriser : 14705773
Facteurs de 14705773 : [3541, 4153]
Divisions : 1182 | Temps : 0.000000 s

Entier à factoriser : 2428216771
Facteurs de 2428216771 : [48341, 50231]
Divisions : 16116 | Temps : 0.003000 s

On notera que le nombre de divisions dépend de l’algorithme utilisé, et selon bien sûr que celui-ci soit plus ou moins optimisé…

Pour que tu puisses utiliser toi-même le programme, facile : tu vas sur > cette page <, tu copies le code Python dans le cadre de gauche, en dessous tu cliques sur ‘Exécuter’, et dans la fenêtre de droite tu as le programme qui te demande de rentrer un nombre. Dès que tu en proposes un et que tu valides avec [Entrée] la réponse t’est donnée. Il suffira de cliquer à nouveau sur ‘Exécuter’ pour relancer le programme et essayer un autre nombre.

okbob852

Membre

Inscription : 12-07-2025

Messages : 38

Re : factorisation avec Python

Le problème est toujours sans résolution
je vais encore l'expliquer

j'ai factoriser le nombre 33762007291
issue de (184511*182981)
nombres d’ope rations pour en arriver est 30752

et quand Ernst le factorise avec python ,il en arrive à 61504 opération
la question pour cet écart entre nous (nombre d’opérations) en plus comme vous le constater c'est le double
y a-il une explication les spécialistes ?

Dernière modification par okbob852 (15-07-2025 19:20:35)

Ernst

Membre

Inscription : 30-01-2024

Messages : 339

Re : factorisation avec Python

Bonsoir,

En fait c'est facile à comprendre, le programme teste toutes les divisions par 2, puis 3, puis par les multiples de 6±1. Or parmi ceux-ci, environ la moitié ne sont pas des nombres premiers. Donc effectivement, le nombre de divisions ici n'est pas un minimum théorique.

Si on ne veut tester que les divisions par des nombres premiers, il faut une liste de ceux-ci jusqu'à la racine carrée du nombre dont on cherche les facteurs. Soit on charge cette liste, soit on la constitue par une méthode rapide similaire à celle utilisée dans le programme (il faut par exemple 16 664 nombres premiers pour pouvoir factoriser ton nombre 33762007291).

Allez hop, programme en Python qui constitue d'abord cette liste puis qui ne compte que les divisions par des nombres premiers :

import math
import time
from collections import defaultdict

def generer_premiers_jusqua(n):
    """Crible d'Eratosthène optimisé avec bytearray"""
    if n < 2:
        return []
    sieve = bytearray([1]) * (n + 1)
    sieve[0:2] = b'\x00\x00'
    for i in range(2, int(math.isqrt(n)) + 1):
        if sieve[i]:
            sieve[i*i::i] = b'\x00' * len(sieve[i*i::i])
    return [i for i, is_prime in enumerate(sieve) if is_prime]

def factoriser_avec_premiers(n, premiers):
    """Factorisation avec comptage précis des divisions"""
    facteurs = defaultdict(int)
    divisions = 0
   
    if n == 1:
        return {}, 0
   
    for p in premiers:
        if p * p > n:
            break
        while True:
            divisions += 1
            quotient, reste = divmod(n, p)
            if reste != 0:
                break
            facteurs[p] += 1
            n = quotient
    if n > 1:
        facteurs[n] += 1
    return dict(facteurs), divisions

def main():
    print("Factorisation efficace avec comptage des divisions")
    print("-----------------------------------------------")
    n = int(input("Entrez un nombre à factoriser : "))
   
    start_total = time.perf_counter()
   
    # Étape 1: Génération des premiers
    start_gen = time.perf_counter()
    racine = math.isqrt(n)
    premiers = generer_premiers_jusqua(racine)
    temps_gen = time.perf_counter() - start_gen
   
    # Étape 2: Factorisation
    start_fact = time.perf_counter()
    facteurs, nb_div = factoriser_avec_premiers(n, premiers)
    temps_fact = time.perf_counter() - start_fact
   
    # Résultats
    print("\n► Résultat :")
    if not facteurs:
        print(f"{n} est premier !")
    else:
        decomp = " × ".join(f"{p}^{e}" if e > 1 else str(p) for p, e in sorted(facteurs.items()))
        print(f"{n} = {decomp}")
   
    print("\n► Performance :")
    print(f"- Nombres premiers générés : {len(premiers)}")
    print(f"- Divisions effectuées : {nb_div}")
    print(f"- Temps génération : {temps_gen:.6f}s")
    print(f"- Temps factorisation : {temps_fact:.6f}s")
    print(f"- TOTAL : {time.perf_counter() - start_total:.6f}s")

if __name__ == "__main__":
    main()
 

Entrez un nombre à factoriser : 33762007291

► Résultat :
33762007291 = 182981 × 184511

► Performance :
- Nombres premiers générés : 16644
- Divisions effectuées : 16583
- Temps génération : 0.005938s
- Temps factorisation : 0.002296s
- TOTAL : 0.020397s

okbob852

Membre

Inscription : 12-07-2025

Messages : 38

Re : factorisation avec Python

Bonjour
merci pour la reponse bien éclairci
je croit que vous esquivez à ma question pour ne pas dire (rechaper)

cette fois ci j'ai choisi un nombres petit de 7 chiffres à factoriser ,le 1653833
afin que ceux qui nous suivent peuvent contribuer à cette discussion
et bien voila ce que j'ai trouve toujours dans le point de (nombre d’opérations)
les deux facteurs sont(1033*1601)
donc j'ai factoriser seulement avec des nombres premiers comme diviseurs
  Divisions effectuées : 80 (ope rations)

dans votre cas en python normalement vous en trouverez le double 160,170 ou presque
j'aimerez bien que vous nous indiquez ce détaille comme vous l'avez fait auparavant 
et si c'est le cas
pourquoi ?

Ernst

Membre

Inscription : 30-01-2024

Messages : 339

Re : factorisation avec Python

Bonjour,

je croit que vous esquivez à ma question pour ne pas dire (rechaper)

Ah bon. Pourtant j'ai vraiment essayé de proposer et d'expliquer. Faut vraiment que j'arrête, moi...

donc j'ai factoriser seulement avec des nombres premiers comme diviseurs
  Divisions effectuées : 80 (ope rations)

Bravo, surtout quand on pense qu'avec mon dernier programme il faut pas moins de 175 divisions pour la même factorisation.

si c'est le cas
pourquoi ?

Oh, tout simplement parce qu'il essaie méthodiquement sans rien négliger, et qu'entre 2 et 1033 inclus il y a exactement 174 nombres premiers.

Ceci dit, j'espère que tu trouveras des interlocuteurs plus à même de te satisfaire, alors bonne continuation.

LEG

Membre

Inscription : 19-09-2012

Messages : 790

Re : factorisation avec Python

Bonjour :
@okbob852 : c'est pourtant facile à comprendre le nombre maximum d'opérations pour factoriser un produit de deux premiers p et q de même taille est égale tout au plus au nombre de premiers p < à la racine carrée du produit.
dans les deux cas que tu as évoqués , c'est au maximum 1) 16 644 opérations , 2) 174 opérations

Donc lorsque tu racontes qu'il n'y a que 80 opération , il est clair que tu ne passes pas , par tous les nombres premiers p < 1033 puisqu'il y en a 174 ...!

Ou alors tu divises ton nombres d'opération par 2.???

Mais est ce qu'au moins tu peux nous écrire ta liste de nombres premiers p , que tu as utilisé ..., car 80 , c'est pas la mer à boire et on y verrai un peu plus clair dans tes allégations....

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 385

Re : factorisation avec Python

RE,

Arriver à "agacer" Ernst, c'est fort...
Bon, alors je prends le relais :

Le nombre 131876058687340818200393 se factorise ainsi :
           155598529759 * 847540519127
Nombre d'essais : 1
Temps de travail : 0.618 s

Allez okbob852, avec cette proposition, fais-le si tu peux ! ^_^
(Ma machine possède 16 Go de RAM, tourne avec windows 7 et Python v. 3.8.10...
Même si mon processeur est un AMD FX 6300 (vitesse 3,6 Ghz) a 6 cœurs, je n'en utilise qu'un....
Elle est donc loin d'être une bête de course.

N-B :
La méthode n'est pas de moi et il arrive qu'elle ne fonctionne pas..

J'en ai développé une il y a quelques années, il  faut que je remette la main dessus...

@+

[EDIT] La méthode utilisée se termine par un calcul de PGCD, qui a été effectué 1 seule fois (essai) dans une boucle.utilisant la fonction gcd du module math...
Je vais la remplacer par la méthode des divisions successives pour tester le nombre de divisions : ce sera sûrement bien moins rapide.
.............
Bon, bin après tests, ça ne va pas être aussi simple que je le pensais de substituer la fonction existante gcd du module math, par la méthode classique apprise en classe de 3e et qui en Python occupe 4 lignes...
Je vois que je vais être obligé de réfléchir...

Dernière modification par yoshi (18-07-2025 18:52:50)

LEG

Membre

Inscription : 19-09-2012

Messages : 790

Re : factorisation avec Python

Bonjour @Yoshi

Ne perds pas trop de temps à réfléchir, pour lui trouver une réponse.

Car : Il existe 6 292 832 119 nombres premiers inférieurs ou égaux à 155 598 529 759 ; ça risque d'être long pour tester tous ces facteurs premiers...^_^ .

De plus , il ne prend même pas la peine de répondre..., ni d'essayer de comprendre ce que lui a posté @Ersnt..

Bonne journée Leg.

Dernière modification par LEG (19-07-2025 06:51:25)

okbob852

Membre

Inscription : 12-07-2025

Messages : 38

Re : factorisation avec Python

bonjour
j'ai décider de ne pas poser trops de questions pourquoi? pourquoi?
mais au lieu je donne des réponses
vous m'avez demander de publier la listes des nombres premiers avec laquelle j'ai trouvé 80 opérations (diviseurs) pour le nombre 1653833
au lieu de 170
la voici
7,  13,  19 ,  31, 37, 43 , 61 ,67,  73 ,79 ,  97,   
103 , 109, 127,139,151, 157 ,163 , 181 , 193 , 199, 211,223, 229,241,271,277 ,283, 307 ,313 , 331, 337 ,349 , 367, 373, 379,397,409 ,421,433, 439, 457, 463, 487, 499, 523 ,541, 547 ,571,577,601, 607 ,613 ,619, 631, 643, 661, 673, 691, 709 ,727, 733, 739 ,751,757, 769  ,787, 811, 823, 829, 853, 859, 877, 883 ,907, 919, 937 ,967 ,991,997,1009,1021, 1033
vous allez me demander ou sont les autre de la mémé série
je répond
j'ai découvert ou j'ai développer un astuce qui divise les nombres premiers en deux catégories les deux sont différentes l'un de l'autre
celle ci est la première catégorie  le reste de cette liste  est la deuxième catégorie 
ily a des nombre qui marche avec la 1ere uniquement et il y a qui marche avec la deuxième
et il y a ceux qui marche avec les deux comme la cas 1653833 qui possédé un nombre avec la 1ere l  le 1033
et un autre avec la deuxième le 1601
et cette calcification aide à minimiser le nombres d’opérations jusqu’à la moitié au lieu de 170 vous aurez 80   
mettez les deux listes en face et vous verrez q'il y une différence entre les deux
essayez cette méthode ,tu ne perd rien

Dernière modification par okbob852 (19-07-2025 11:08:41)

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 385

Re : factorisation avec Python

RE,

@LEG
Le nombre 131876058687340818200393 que j'ai proposé a été factorisé en 0,618 s...
Le nombre de tours de tours de la boucle while d=1: du programme ci-dessous est de 291552 (donc le nombre d'appels au calcul du PGCD) est probablement sous-évalué

@okbob852
Si je veux comparer ce qui est comparable, le nombre 1653833 nécessite 10 appels au calcul du PGCD mais il est composé de seulement 7 chiffres, le mien de 24 !!! ...
De tous les nombres testés qui figurent dans le code, seul le premier ne m'a pas permis d'obtenir un résultat : en fait, je n'ai pas eu la patience d'attendre...
Alors okbob852, penses-tu pouvoir - avec ta méthode -
1. Décomposer le nombre 131876058687340818200393 que j'ai proposé
2. En un temps raisonnable  ?

# usr/bin/env python
# -*- coding: utf-8 -*-

from time import time
from math import gcd

tp_d=time()
#n=19283635235010757318836917200237668345470484572549790364309671655196725561403266082609
#n=418446744073709551617
#n=10023859281455311421
#n=1653833
#n=22214069
#n=58618633
#n=228232597
#n=493376993
#n=8081693687
#n=9044391781
#n=1653833
n=131876058687340818200393

# Si la factorisation me marche pas
# Et si vous avez la certitude que votre nombre n'est pas premier
# Changez la valeur de c : essayez avec 3,5,7 objet de la boucle for...
# N-B le programme proposé reprend la suggestion et teste (au cas où) les valeurs de c de 2 à 11 (exclu)

def pollardrho(n, cmax):
    global nb_d_c
    """Factorisation d'un nombre entier décomposable (méthode Rho de John Michael Pollard)"""
    x, y, d, nb_d_c = 2, 2, 1, 0
    for c in range(1, cmax):
        f = lambda z: z*z + c
        while d == 1:
            nb_d_c+=1
            x = f(x) % n
            y = f(f(y)) % n
            d = gcd(x-y, n) # ligne que je veux remplacer pour permettre de calculer le nombre de divisions successives          
        if d != n:
            return [d, n//d] # ici, on a trouvé une décomposition non triviale
    return [d, n//d] # ici, il est possible que la décomposition ait échoué

temps = time()-tp_d
print ("Le nombre",n,"se factorise ainsi :")
print ("          ",nb1,"*",nb2)
print ("Nombre de calculs de PGCD :",nb_d_c)
print ("Temps de travail :", round(temps,3),"s")
 

Méthode originale :
https://fr.wikipedia.org/wiki/Algorithme_rho_de_Pollard
qui a inspiré :
https://python.jpvweb.com/python/mesrec … pollardrho

@+

Dernière modification par yoshi (19-07-2025 15:10:39)

LEG

Membre

Inscription : 19-09-2012

Messages : 790

Re : factorisation avec Python

Bonjour :

@okbob852 ; je te cite :

je répond
j'ai découvert ou j'ai développer un astuce qui divise les nombres premiers en deux catégories les deux sont différentes l'un de l'autre...

Bravooooo... , personne n'y avait pensée depuis plus de 2000 ans ¨_¨.  ,

Tu as découvert que les nombres premiers et leurs multiples sont de la forme 6k +1 ou 6k - 1

Donc si un des facteurs de ton produit, n'est ""ou ne sont"" pas de la première forme , ton astuce permet donc , d'affirmer qu'ils sont de la deuxième forme ...

Tu devrais publier ta découverte...

Mais surtout nous dire comment tu sais , qu'un des deux facteurs premiers, celui qui est inférieur à la racine de ton produit est de la première forme ou de la deuxième...?

Car effectivement ce n'est pas la peine de s'em.... avec l'autre catégorie de facteurs premiers, on en supprime la moitié...

Moi ; j'ai réussi à les partager en huit catégories ... pour ne faire que 20 opérations au lieu de 80 ,

Ben oui : 1033 et de la forme ou catégorie 30k +13 (13, 43 , 73 , 103, 163 ,.....etc.. 823 , 853 et 1033.
Mets les 8 catégories l'une en face de l'autre, tu verras qu'il y a une différence ...

Dons tu vas pouvoir maintenant , faire mieux, pour décomposer le nombre de  @Yoshi.... Très rapidement ..., on a hâte de voir ta réponse.

Tu verras , tu va faire plein de découvertes .... Ce qui devrait te donner le temps de réfléchir, avant de poursuivre ton  sujet....

Dernière modification par LEG (20-07-2025 09:05:51)

okbob852

Membre

Inscription : 12-07-2025

Messages : 38

Re : factorisation avec Python

bonjour
Je m'excuse yoshi de ne pas pouvoir te répondre sur ton nombre volumineux , car la factorisation elle mémé n'est pas mon intérêt ( chercher les deux nommes premier composants ce tel ou tel nombre ), et aussi la durée de cette opération
ce qui m’intéresse le plus et je fais des recherche c'est le nombre premier lui même comme diviseur ,et comment on peut le réduire à moitié
comme le cas de 80 diviseur au lieu de 170 , et même le réduire  ce 170 à 26

et je doit remercier Ernst qui m'a aider à montrer bien ce problème avec ces fiches ( pédagogique ) en python

et je n'ai pas pu vous dire autant sur cette méthode qui reduit les diviseur à moitie ou encore le quart  ;je voudrais la certifier à mon nom comme propriété intellectuelle ,
je voudrais vous informer vous qui s’intéressent à tout ce qui est math ,que cette méthode existe
merci à tous

Dernière modification par okbob852 (20-07-2025 09:32:40)

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 385

Re : factorisation avec Python

Bonjour,

Donc, si j'ai bien compris, okbob852, tu ne n'intéresses aux nombres premiers que comme diviseurs premiers permettant de factoriser n'importe quel nombre proposé qui te serait proposé en utilisant une quantité moindre (moitié, voire quart) ?
Tout ça pour pouvoir valoriser ta découverte...

N'as-tu l'impression d'être face à une contradiction ?

En effet, quel est l'intérêt de ta méthode si tu ne t'intéresses qu'à l'aspect  : << Moi, j'en utilise deux fois (voire quatre fois) moins que vous pour factoriser n'importe quel nombre (non premier) produit de deux nombres premiers ! >>
Une méthode n'est considérée comme valable que si
- soit elle marche toujours et en apporter une preuve mathématique irréfutable,
- soit elle ne marche que sur un intervalle donné, et donc de disposer des  composants dudit nombre factorisé...

Or, toi, ces composants ne t'intéressent pas...
Quelle avancée représente ta méthode, si pour factoriser un nombre volumineux, en utilisant l'algorithme Rho de John Michael Pollard, on n'est dépendant d'aucun prérequis de connaissance de nombres premiers et qu'on n'en utilise... aucun et ce tout en allant incomparablement plus vite ?
Tu ne peux pas décomposer n=131876058687340818200393 en un temps raisonnable (allez, disons plusieurs heures...)
Dommage... La méthode Rho ne met, elle, que 6/10e s pour donner la réponse...

Et si tu arrivais à le faire, puisque les deux diviseurs premiers de 131876058687340818200393 ne t'intéressent pas, pour être  logique avec toi-même, tu te ferais un devoir de ne pas les utiliser, comment ferais-tu ?

@+