Comment trouver efficacement tous les facteurs d'un nombre en Python ?

Trouver les facteurs d'un nombre en Python avec une efficacité maximale

Trouver tous les facteurs d'un nombre peut être une tâche difficile, en particulier lorsqu'il s'agit de grands nombres. Cet article explore une méthode efficace pour y parvenir dans Python 2.7.

Approche optimale utilisant la factorisation

Pour trouver tous les facteurs d'un nombre, la clé est de le décomposer dans ses facteurs premiers. Une fois que vous connaissez les facteurs premiers, trouver le reste des facteurs est simple.

L'extrait de code ci-dessous utilise cette approche :

<code class="python">from functools import reduce

def factors(n):
    return set(reduce(
        list.__add__,
        ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))</code>

Cette fonction accepte un nombre n et renvoie un ensemble contenant tous ses facteurs.

Comprendre l'algorithme

Le cœur de l'algorithme réside dans la compréhension [i, n//i] pour i dans la plage (1, int(sqrt(n)) 1) if n % i == 0. Cette partie génère des paires de facteurs.

Pour chaque nombre i de 1 à la racine carrée de n, il vérifie si n est divisible par je sans reste. Si tel est le cas, il inclut à la fois i et n//i dans la paire puisqu'ils sont tous deux facteurs de n.

Optimisation de la plage de recherche

La raison pour laquelle nous recherchons jusqu'à la racine carrée de n est que si i est un facteur de n, alors son facteur de paire n//i doit également être trouvé dans cette plage. Cela garantit que nous ne manquerons aucun facteur.

Gestion des doublons

Étant donné que les carrés parfaits ont des facteurs en double (par exemple, 4 a des facteurs 2 et 2), l'ensemble ( ...) à la fin de l'extrait de code supprime tous les doublons de la liste des paires. Cela garantit que nous obtenons un ensemble propre de facteurs uniques.

Exemple d'utilisation

Pour utiliser cette fonction, transmettez simplement le nombre que vous souhaitez factoriser comme argument :

<code class="python">result = factors(24)  # -> {1, 2, 3, 4, 6, 8, 12, 24}</code>

Cela renverra un ensemble contenant tous les facteurs du nombre 24.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!