Décomposition en facteurs premiers ver.1 des entiers entrés en Python

introduction

Le "[Programme pour déterminer si un nombre entré en Python est un nombre premier] créé précédemment](https://qiita.com/totusuna/items/9ae6ada058fa4e9cd6f9)" a une fonction qui effectue une décomposition en facteurs premiers lorsqu'il s'agit d'un nombre composé. Je l'ai ajouté.

Principe du programme

Rappelant la méthode de décomposition des facteurs premiers que j'ai apprise à l'école primaire, j'ai décidé de continuer à diviser à partir du plus petit nombre premier. Plus précisément, créez une liste de nombres premiers en utilisant la gamme d'amorce de SymPy et continuez à diviser par un nombre divisible à partir de cette liste. Ensuite, lorsque la division a été effectuée jusqu'à la fin de la liste des nombres premiers, elle était terminée.

Programme réel

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

for i in primlist:
    while n % i == 0: #2
        n /= i
        yaku.append(i) #3

if not yaku: #4
    print(n, "Est un nombre premier.")
else:
    print(inn, "Est un nombre composé, et lorsqu'il est décomposé en facteurs premiers",yaku, "est.")

Écoulement brutal

1. Créez une liste de nombres premiers jusqu'à (n + 1) / 2
2. Trouvez un nombre divisible dans la liste des nombres premiers et continuez à diviser l'entier n jusqu'à ce qu'il ne soit plus divisible.
3. Chaque fois que vous divisez, ajoutez le nombre premier divisé à la liste appelée yaku.
4. S'il n'y a rien dans yaku, il est affiché sous forme de nombre premier. Si quelque chose est inclus, le résultat de la factorisation prime est affiché.

Ce que tu fais réellement

1. Créé en # 1 en utilisant Sympy comme avant.
2. Dans # 2, en utilisant la syntaxe while, il est possible de mettre en marche l'opération de continuer à diviser immédiatement sans utiliser if.
3. Dans # 3, ajoutez le premier i divisé par yaku en faisant .append (i).
4. Au n ° 4, j'ai remarqué que si yaku contient un nombre, c'est un nombre composé. Plus précisément, si vous utilisez la syntaxe if et définissez if ** not ** yaku, lorsqu'il n'y a rien dans yaku, le traitement ci-dessous sera lancé.

Des difficultés

Lors de la première programmation, la plage de la liste de nombres premiers créée par primerange () était la même que la fois précédente, "primerange (2, int (n ** (1/2)) + 1)". Ensuite, lorsque l'entier d'entrée était "2 x nombre premier", seulement 2 était ajouté à yaku, et il y avait un problème que la factorisation premier ne pouvait pas être effectuée avec précision. Plus précisément, lorsque j'ai entré un nombre tel que 14 (2 × 7), le résultat était "14 est un nombre composé, et décomposé en facteurs premiers, il est [2]. ] Est sorti. Par conséquent, j'ai défini la plage de la liste des nombres premiers sur "plage principale (2, (inn + 1) / 2)". En faisant cela, j'ai décidé de résoudre le problème précédent. A ce moment, en ajoutant +1 à inn, une liste de nombres premiers peut être créée jusqu'à un nombre premier même avec un entier de "2 x nombre premier". Plus précisément, lorsque 14 est entré, il devient la plage d'amorces (2, 7,5), de sorte que le contenu de la liste primaire devient [2, 3, 5, 7]. Si vous ne faites pas +1, vous obtiendrez la plage d'amorces (2, 7), de sorte que le contenu de la primelist sera [2, 3, 5] et 7 ne sera pas inclus dans le résultat de la factorisation première, donc une factorisation première précise Cela ne sera pas possible.

Réflexions

Si la plage de création de la liste des nombres premiers est trop large et que l'entier d'entrée devient grand (7 chiffres ou plus), la vitesse de calcul diminuera immédiatement. Par conséquent, je voudrais améliorer un peu le réglage de la plage et la méthode de décomposition des facteurs premiers. Merci d'avoir lu jusqu'au bout.