Je m'initie en Python dernièrement, et j'ai eu l'idée de concevoir un programme qui fait la décomposition d'un entier en facteurs premiers.

Le problème vient du fait que pour des entiers relativement "lourds", le temps d'exécution est vite très long.

Aperçu du code:

from time import time
def pchk(n):
    i=2
    while i <= int(n**0.5):
        while n%i==0:
            return 0
        i=i+1
    return 1
def text(i,j):
    return i,j
print("Légende : (i, j) = i exposant j")
while 0 == 0:
    n=int(input("Donner un entier :"))
    start = time()
    i = 2
    j = 0
    k = 0
    N = abs(n)
    if n < -1:
        n = -1*n
        print(-1*n,"= -1×",end=" ")
    else:
        print(n,"=",end=" ")
    while i <= n:
        if N == 1 or N == 0:
            print(n)
            break
        if pchk(N) == 1:
            print(N)
            break
        if pchk(n) == 1:
            print(int(n),end="")
            break
        if n%i == 0 and pchk(i) == 1:
            while n%i == 0:
                j += 1
                n = n/i
            if 0 < k and n != N / (i**j):
                print(" × ",end="")
            if j == 1:
                print(i,end="")
            elif j > 1:
                print(text(i,j),end="")
        j = 0
        i += 1
        k += 1
    print()
    print("Temps d'exécution :", time() - start, "s")
    print("\n")

Des idées pour optimiser ceci?

Sincèrement j'arrive pas à voir ce qui se passe dans ton code. Il y a beaucoup beaucoup trop d'informations. Voici le code que j'ai pondu qui n'utilise que 3 variables. Peut-être pourra-t-il mieux t'orienter sur ton problème que je ne puisse le faire:

def decomposition(nb):
    i, nb_premier = 2, []
    if nb <= 0:
        return nb_premier
    while nb != 1:
        while not nb%i:
            nb_premier.append(i)
            nb = nb//i
        i += 1
    return nb_premier

#Et à l'utilisation
print(decomposition(1000000000))

-
Edité par Olygrim 22 décembre 2015 à 11:20:17

Tu peux encore faire quelques améliorations sur ton code Olygrim:

def primeFactors(n):
    Decomp = []
    # 1 n'a pas de décomposition non plus parce que 1 n'est pas premier.
    if n <= 1:
        return Decomp
    # Tant que notre nombre est divisible par 2 (le dernier bit du nombre est un 0 <=> le nombre est divisible par 2):
    while not n & 1:
        Decomp.append(2)
        # Décaler sur la droite de 1 bit revient à diviser (division entière) par 2
        n >>= 1
    
    # Maintenant on est sur que notre nombre n'est pas divisible par 2 donc on n'a plus qu'à tester les nombres impairs:
    k = 3
    while n != 1:
        while not n%k:
            Decomp.append(k)
            n //= k
        k += 2
    # Ici on a trouvé tous les facteurs premiers, donc on retourne:
    return Decomp

Après quelques tests ça permet d'améliorer un tout petit peu la performance

Sinon arkolord, voici quelques remarques:

• Un enchaînement de "if" avec des break => C'est moche.
• Une fonction nommée pchk => Incompréhensible pour quelqu'un qui survole ton code. Donne des noms de fonction plus longs, mais plus compréhensible IDEM pour tes variables i,j,k.
• "while 0 == 0" => Autant mettre un "while True", mais même ça c'est pas une bonne idée. Les boucles infinies, même avec des break à l'intérieur, c'est (presque) jamais une bonne idée.

Si tu ne comprends pas pourquoi l'exemple de Olygrim ou le mien marchent correctement alors fait le nous savoir, il y a quelques théorèmes mathématiques cachés derrière nos choix de programmation.

Voici une autre solution

from math import sqrt, ceil

def decomposition(n):
    facteurs = []
    while n%2==0 and n>0:
        facteurs.append(2)
        n /= 2
    
    for i in range(3, ceil(sqrt(n)), 2):
        while n%i == 0:
            facteurs.append(i)
            n /= i
    
    if n > 1:
        facteurs.append(n)
    
    return facteurs

print(decomposition(1000000000))

Qui est je pense loin d'être la meilleure à y réfléchir

-
Edité par Anonyme 22 décembre 2015 à 14:12:32

Merci pour vos remarques !

Cependant, j'insiste sur le fait que j'ai besoin d'un affichage "naturel" au maximum, c-à-d avec l'opérateur "×" et les exposants, d'où mon usage d'un nombre conséquent de variables.

En ce qui concerne les listes... je ne les maîtrise pas encore. Ainsi, mon code semble élémentaire.

J'ai l'ai un peu "amélioré": variables avec des noms explicites, boucles inutiles supprimées, etc.

Aperçu:

from time import time
def primecheck(n):
    i=2
    while i <= int(n**0.5):
        while n%i==0:
            return 0
        i=i+1
    return 1
n=int(input("Donner un entier :"))
start = time()
prime = 2
exposant = 0
compteur = 0
N = abs(n)
if primecheck(abs(n)) == 1 or abs(n) == 0 or abs(n) == 1:
    print(n,"=",n)
else:
    if n < -1:
        n = -1*n
        print(-1*n,"= -1 ×",end=" ")
    else:
        print(n,"=",end=" ")
    while prime <= n:
        if n%prime == 0 and primecheck(prime) == 1:
            while n%prime == 0:
                exposant += 1
                n /= prime
            if 0 < compteur and n != N / (prime**exposant):
                print(" × ",end="")
            if exposant == 1:
                print(prime,end="")
            elif exposant > 1:
                print(prime,"^",exposant,end="")
        elif primecheck(n) == 1:
            print(" ×",int(n),end="")
            break
        exposant = 0
        if prime == 2:
            prime += 1
            compteur += 1
        else:
            prime += 2
            compteur += 2
    print()
    print("Temps d'exécution :", time() - start, "s")
    print("\n")

PS: Superbe l'idée des nombres premiers impairs !

-
Edité par arkolord 22 décembre 2015 à 16:07:46

ton algorithme me parait bien long, comparer a celui que j'ai trouve sur internet :

Cependant, j'insiste sur le fait que j'ai besoin d'un affichage "naturel" au maximum, c-à-d avec l'opérateur "×" et les exposants, d'où mon usage d'un nombre conséquent de variables.

En ré-utilisant la fonction que j'ai déjà définie et des built-in Python:

def afficherDecomposition(n):
    factors = primeFactors(n)

    # On formate les facteurs pour qu'ils apparaissent bien:
    # Ici on enlève les doublons de la liste factors
    setFactor = set(factors)
    # On met tous les facteurs premiers sous la forme "a^{nombre d'occurence de a dans la liste des facteurs premiers}"
    numbersWithExp = [str(n)+"^"+str(factors.count(n)) for n in setFactor]
    # Finalement on regroupe tous les facteurs entre eux:
    finalString = '×'.join(numbersWithExp)

    # On affiche le résultat:
    print("Voici la décomposition en facteurs premiers du nombre {} : {}".format(n, finalString))

Quelques tests pour vérifier que ça marche bien:

In [15]: afficherDecomposition(100)
Voici la décomposition en facteurs premiers du nombre 100 : 2^2×5^2

In [16]: afficherDecomposition(1006)
Voici la décomposition en facteurs premiers du nombre 1006 : 2^1×503^1

In [17]: afficherDecomposition(84923846749039264840)
Voici la décomposition en facteurs premiers du nombre 84923846749039264840 : 6977^1×2^3×5^1×487^1×863879^1×881^1×821^1

Avec quelques petits réglages tu peux facilement enlever les "^1" qui traînent et/ou trier les facteurs premiers dans l'ordre croissant. Si tu ne vois pas comment ou que tu n'es pas familier avec les chaînes de caractère, n'hésite pas à nous poser des questions

Maintenant passons à l'analyse de ton code:

• Ta fonction primecheck n'est pas optimisée. Si la rapidité d'exécution t'importe, alors fait le nous savoir et on pourra t'aiguiller vers quelques optimisations utiles
• Tu calcules la valeur absolue de \( n\) pour la mettre dans la variable \(N\), mais juste après tu n'utilises pas cette variable et tu re-calcule la valeur absolue Sûrement une erreur d'inattention
• Les valeurs 1 et 0 dans ta fonction primecheck peuvent être remplacées par True ou False. Sémantiquement parlant c'est bien plus expressif, et en plus ça t'évites tout pleins de tests dans ton premier if.
• Essaie ton algorithme avec n=-1. Tu vas voir, normalement ça plante.
• prime et compteur sont toutes les deux incrémentées et initialisées aux mêmes moments. Es-tu certains que tu as besoin de ces deux variables?

Si on va plus loin que ton code, l'algorithme en lui même est un peu compliqué et effectue des comparaisons/boucles inutiles. C'est plus du domaine des mathématiques donc on fonction de ton niveau/intérêt en maths on peut éventuellement t'aider à perfectionner ce point aussi

EDIT:

Olygrim a écrit:

@Nelimee: Pas mal l'idée de retirer les nombres pairs. Pour un grand nombre premier, ça peut faire une grosse différence (un facteur 2) 

Dans la pratique pas spécialement. Voici quelques temps d'exécutions pour différentes valeurs. J'ai prit ton code, le code de oldProgrammer et le mien:

• Pour 10**4:
  Olygrim: 4.22µs
  oldProgrammer: 9.28µs
  Nelimee: 3.83 µs
• Pour 10**8:
  Olygrim: 6.95 µs
  oldProgrammer: 82.3 µs
  Nelimee: 6.61 µs
• Pour 10**16:
  Olygrim: 13.2 µs
  oldProgrammer: 47.6 ms
  Nelimee: 12 µs
• Pour 10**32:
  Olygrim: 29.6 µs
  oldProgrammer: 9.07 s
  Nelimee: 24.5 µs
• Pour 10**128:
  Olygrim: 181 µs
  oldProgrammer: trop long désolé
  Nelimee: 115 µs

C'est dans les résultats de temps d'exécution qu'on voit que la boucle "for" sans "break" est vraiment pas géniale. Pour te donner une idée oldProgrammer, voici le nombre de boucle effectuées par les programmes pour 10**128:

• Olygrim: 260
• Nelimee: 258 (petite différence avec Olygrim, je ne comprends pas encore pourquoi c'est si petit alors que j'incrémente deux fois plus vite ^^)
• oldProgrammer: \( \sqrt{10^{128}} = 10^{64} \approx 3.85 * 10^{61} * 260 \).

Si tu rajoutes un break dans ta boucle for on passe de suite à des valeurs bien inférieures: 25489850 boucles et un temps d'exécution encore mesurable, environ 11.1 secondes. Encore une fois je ne comprends pas pourquoi il y autant de boucles puisque ton algorithme avec un petit break en plus est très semblable à celui de Olygrim et au mien... Une étude plus approfondie me donnera peut-être la réponse

EDIT 2: Au final avec des nombres de l'ordre \( 10^{512} \) on obtient bel et bien un facteur 2 entre nos deux temps d'exécution Olygrim Même un facteur 3 pour des nombres de l'ordre de \( 10^{4096} \) (oui je vais loin :p).

-
Edité par Anonyme 22 décembre 2015 à 18:31:07

Et un itérable, pour rester original ?

from collections import defaultdict


def iter_factors(n):
    while not n % 2:
        yield 2
        n //= 2
    for x in range(3, int(n**0.5), 2):
        while not n % x:
            yield x
            n //= x
        if n == 1:
            break
    else:
        yield n


def print_factors(n):
    factors, equal = defaultdict(int), '= -1 ×' if n < 0 else '='
    print(n, equal, end='\r', flush=True)
    for prime in iter_factors(abs(n)):
        factors[prime] += 1
        products = ' × '.join(
            '{}^{}'.format(p, e) if e > 1 else str(p)
            for p, e in sorted(factors.items())
        )
        print(n, equal, products, end='\r', flush=True)
    print()


if __name__ == '__main__':

    from time import time

    try:

        while True:
            s = input('Entrez un nombre entier: ')
            try:
                n = int(s)
                break
            except ValueError:
                print("Erreur: {} n'est pas un nombre entier !".format(s))

        start = time()
        print_factors(n)
        end = time()
        print("Temps d'exécution :", end - start, 'secondes.')

    except KeyboardInterrupt:
        pass

EDIT: correction algorithmique...

-
Edité par Anonyme 22 décembre 2015 à 22:05:47

C'est dans les résultats de temps d'exécution qu'on voit que la boucle "for" sans "break" est vraiment pas géniale. Pour te donner une idée oldProgrammer, voici le nombre de boucle effectuées par les programmes pour 10**128:

Oui je m'en doutais

@Nelimee: C'est pratiquement le même temps car tu prends des nombres facilement divisible (par 2 et 5). Prends un grand nombre premier, et je pense que la différence sera rapidement visible.

Edit: Teste avec ce nombre premier-ci: 100000073 ou encore 1000000087

-
Edité par Olygrim 22 décembre 2015 à 20:22:26