introduction

Le problème que le temps d'exécution est long lorsque l'entier d'entrée est un nombre premier dans la [Décomposition du facteur premier ver.1 de l'entrée entière en Python] précédemment créée (https://qiita.com/totusuna/items/87a10755a25dc310c17a) Résoudre.

Programme réel

from sympy import primerange
 inn = n = int (input ("Veuillez saisir le nombre que vous voulez vérifier s'il s'agit d'un nombre premier. >>"))
num = int(n**(1/2)) + 1
primlist = list(primerange(2,num)) 
yaku = []

for i in primlist:
    if inn % i == 0: #1
 print (inn, "est un nombre composé.")
        for i in list(primerange(i, (n +1)/i)):  #2
            if n == 1:　#3
                break
            while n % i == 0:
                n /= i
                yaku.append(i)

 print ("La décomposition du facteur premier est", yaku, ".")
        break
    elif i == primlist[-1] :
 print (inn, "est un nombre premier.")

point de changement

Afin de résoudre le problème selon lequel le jugement lorsqu'il s'agit d'un nombre premier est trop lent, il est jugé si l'entier entré avant d'effectuer la décomposition des facteurs premiers en # 1 est un nombre premier. S'il s'agit d'un nombre composé, le traitement à partir du n ° 2 est effectué. La syntaxe if de # 3 a été ajoutée pour afficher le résultat immédiatement lorsque la factorisation des nombres premiers de n est terminée avant d'aller à la fin de la liste des nombres premiers.

Comparaison de vitesse

Le temps a été mesuré en utilisant %% timeit dans Jupyter Notebook. Nous avons utilisé 2281607 comme nombre premier à 7 chiffres et 5241234 (2 x 3 x 873539) comme nombre composé à 7 chiffres. nombre premier ver.1：1.98 s ± 30.2 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) ver.2：1.17 ms ± 25.9 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

Nombre composé ver.1：4.63 s ± 40.1 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) ver.2：4.56 s ± 75.2 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Considération

La vitesse d'exécution lorsqu'un nombre premier est entré est de 1,98 ** s ** → 1,17 ** ms **, ce qui représente une amélioration de vitesse significative. Cependant, lorsque le nombre de composites a été entré, la méthode de traitement proprement dite n'a pas changé, donc aucune amélioration n'a été observée puisque 4,63 s → 4,56 s.

Réflexions

Je suis satisfait pour l'instant car j'ai pu améliorer la vitesse d'exécution alors qu'il s'agissait d'un nombre premier, qui était l'objectif cette fois. Cependant, si nous n'améliorons pas la méthode de factorisation des nombres premiers, nous ne pouvons pas améliorer la vitesse essentielle, c'est pourquoi je voudrais aborder ce point. Merci d'avoir lu jusqu'au bout.