Python Trouver les facteurs premiers

Question

Question en deux parties :

1. En essayant de déterminer le plus grand facteur premier de 600851475143, j'ai trouvé ce programme en ligne qui semble fonctionner. Le problème est que j'ai du mal à comprendre comment il fonctionne exactement, bien que je comprenne les bases de ce que fait le programme. Aussi, j'aimerais que vous puissiez m'éclairer sur toute méthode que vous connaissez pour trouver des facteurs premiers, peut-être sans tester chaque nombre, et sur la manière dont votre méthode fonctionne.

Voici le code que j'ai trouvé en ligne pour la factorisation des nombres premiers. [NOTE : Ce code est incorrect. Voir la réponse de Stefan ci-dessous pour un meilleur code]. :

n = 600851475143
i = 2
while i * i < n:
     while n % i == 0:
         n = n / i
     i = i + 1

print(n)

#takes about ~0.01secs

2. Pourquoi ce code est-il tellement plus rapide que ce code, qui sert juste à tester la vitesse et n'a pas d'autre but réel que celui-là ?

   i = 1 while i < 100: i += 1

   takes about ~3secs

Answer 1

Cette question est le premier lien qui est apparu lorsque j'ai fait une recherche sur Google. "python prime factorization" . Comme le souligne @quangpn88, cet algorithme est faux ( !) pour des carrés parfaits tels que n = 4, 9, 16, ... Cependant, la correction de @quangpn88 ne fonctionne pas non plus, car elle donnera des résultats incorrects si le plus grand facteur premier apparaît 3 fois ou plus, par ex, n = 2*2*2 = 8 o n = 2*3*3*3 = 54 .

Je crois qu'un algorithme correct de force brute en Python est.. :

def largest_prime_factor(n):
    i = 2
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
    return n

Ne l'utilisez pas dans du code de performance, mais c'est correct pour des tests rapides avec des nombres modérément grands :

In [1]: %timeit largest_prime_factor(600851475143)
1000 loops, best of 3: 388 µs per loop

Si l'on cherche la factorisation complète des nombres premiers, il s'agit de l'algorithme de force brute :

def prime_factors(n):
    i = 2
    factors = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors

Answer 2

Ok. Donc, vous avez dit que vous comprenez les bases, mais vous n'êtes pas sûr de savoir EXACTEMENT comment cela fonctionne. Tout d'abord, c'est une excellente réponse à la question du Projet Euler dont elle découle. J'ai fait beaucoup de recherches sur ce problème et c'est de loin la réponse la plus simple.

Pour les besoins de l'explication, je vais laisser n = 20 . Pour exécuter le vrai problème du projet Euler, soit n = 600851475143 .

n = 20 
i = 2

while i * i < n:
    while n%i == 0:
        n = n / i
    i = i + 1

print (n)

Cette explication utilise deux while boucles. La chose la plus importante à retenir concernant while les boucles sont exécutées jusqu'à ce qu'elles ne soient plus true .

La boucle externe indique que pendant que i * i n'est pas supérieure à n (parce que le plus grand facteur premier ne sera jamais plus grand que la racine carrée de n ), ajoutez 1 à i après l'exécution de la boucle interne.

La boucle interne indique que pendant que i n , remplacer n avec n divisé par i . Cette boucle tourne en continu jusqu'à ce qu'elle ne soit plus vraie. Pour n=20 y i=2 , n est remplacé par 10 puis à nouveau par 5 . Parce que 2 ne se divise pas uniformément en 5 la boucle s'arrête avec n=5 et la boucle extérieure se termine, produisant i+1=3 .

Enfin, parce que 3 au carré est supérieure à 5 la boucle extérieure n'est plus true et imprime le résultat de n .

Merci d'avoir posté ce message. J'ai regardé le code pendant une éternité avant de réaliser comment cela fonctionnait exactement. J'espère que c'est ce que vous attendez d'une réponse. Si ce n'est pas le cas, faites-le moi savoir et je pourrai vous expliquer davantage.

Answer 3

On dirait que les gens font le projet Euler, où l'on code soi-même la solution. Pour tous les autres qui veulent travailler, il y a l'option module primefac qui fait de très grands nombres très rapidement :

#!python

import primefac
import sys

n = int( sys.argv[1] )
factors = list( primefac.primefac(n) )
print '\n'.join(map(str, factors))

Answer 4

Pour la génération de nombres premiers, j'utilise toujours le Le tamis d'Eratosthène :

def primes(n):
    if n<=2:
        return []
    sieve=[True]*(n+1)
    for x in range(3,int(n**0.5)+1,2):
        for y in range(3,(n//x)+1,2):
            sieve[(x*y)]=False

    return [2]+[i for i in range(3,n,2) if sieve[i]]

In [42]: %timeit primes(10**5)
10 loops, best of 3: 60.4 ms per loop

In [43]: %timeit primes(10**6)
1 loops, best of 3: 1.01 s per loop

Vous pouvez utiliser Test de primauté de Miller-Rabin pour vérifier si un nombre est premier ou non. Vous pouvez trouver ses implémentations Python aquí .

Utilisez toujours timeit pour chronométrer votre code, le deuxième module prend juste 15us :

def func():
    n = 600851475143
    i = 2
    while i * i < n:
         while n % i == 0:
            n = n / i
         i = i + 1

In [19]: %timeit func()
1000 loops, best of 3: 1.35 ms per loop

def func():
    i=1
    while i<100:i+=1
   ....:     

In [21]: %timeit func()
10000 loops, best of 3: 15.3 us per loop

Answer 5

"""
The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

"""

from sympy import primefactors
print(primefactors(600851475143)[-1])