Python Trouver Les Facteurs Premiers

Ok. Donc, vous l'avez dit vous comprenez les bases, mais vous ne savez pas EXACTEMENT comment il fonctionne. Tout d'abord, c'est une excellente réponse au Projet d'Euler question, il provient. 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 Projet réel d'Euler problème, laissez 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 à propos de while boucles est qu'elles utilisent jusqu'à ce qu'ils ne sont plus true.

La boucle externe précise que, bien que i * i n'est pas plus grand que n (parce que le plus grand facteur premier ne sera jamais plus grand que la racine carrée de n), ajouter 1 à i après la boucle s'exécute.

La boucle interne précise que, bien que i divise de manière égale n, remplacer n avec n divisé par i. Cette boucle s'exécute en continu jusqu'à ce qu'il n'est plus vrai. Pour n=20 et i=2, n est remplacé par 10, puis de nouveau par 5. Parce que 2 ne divisent en 5, la boucle s'arrête avec n=5 et la boucle externe, les finitions, la production de i+1=3.

Enfin, parce que 3 carré est plus grand que 5, la boucle externe n'est plus true et imprime le résultat de n.

Merci pour ce détachement. J'ai regardé le code pour toujours avant de se rendre compte exactement comment il a travaillé. Espérons-le, c'est ce que vous cherchez dans une réponse. Si non, laissez-moi savoir et je peux l'expliquer davantage.

Pour le premier numéro de génération, j'ai toujours utiliser Crible 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 De Miller-Rabin test de primalité pour vérifier si un nombre est premier ou pas. Vous pouvez trouver ses implémentations de Python ici.

Toujours utiliser timeit module pour le temps de votre code, le 2ème 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

Le code n'est pas correct à 100. Il doit vérifier les cas i * i = n:

Je pense qu'il devrait être:

while i * i <= n:
    if i * i = n:
        n = i
        break

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

print (n)

"""
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]

Mon code:

# METHOD: PRIME FACTORS
def prime_factors(n):
    '''PRIME FACTORS: generates a list of prime factors for the number given
    RETURNS: number(being factored), list(prime factors), count(how many loops to find factors, for optimization)
    '''
    num = n                         #number at the end
    count = 0                       #optimization (to count iterations)
    index = 0                       #index (to test)
    t = [2, 3, 5, 7]                #list (to test)
    f = []                          #prime factors list
    while t[index] ** 2 <= n:
        count += 1                  #increment (how many loops to find factors)
        if len(t) == (index + 1):
            t.append(t[-2] + 6)     #extend test list (as much as needed) [2, 3, 5, 7, 11, 13...]
        if n % t[index]:            #if 0 does else (otherwise increments, or try next t[index])
            index += 1              #increment index
        else:
            n = n // t[index]       #drop max number we are testing... (this should drastically shorten the loops)
            f.append(t[index])      #append factor to list
    if n > 1:
        f.append(n)                 #add last factor...
    return num, f, f'count optimization: {count}'

Qui j'ai comparé le code le plus de voix, qui a été très rapide

    def prime_factors2(n):
        i = 2
        factors = []
        count = 0                           #added to test optimization
        while i * i <= n:
            count += 1                      #added to test optimization
            if n % i:
                i += 1
            else:
                n //= i
                factors.append(i)
        if n > 1:
            factors.append(n)
        return factors, f'count: {count}'   #print with (count added)

TESTS, (remarque, j'ai ajouté un compte dans chaque boucle pour tester l'optimisation)

# >>> prime_factors2(600851475143)
# ([71, 839, 1471, 6857], 'count: 1472')
# >>> prime_factors(600851475143)
# (600851475143, [71, 839, 1471, 6857], 'count optimization: 494')

Je l'ai trouver ce code peut être modifié facilement pour obtenir le (facteur le plus important) ou tout ce qui est nécessaire. Je suis ouvert à toutes questions, mon objectif est d'améliorer ce beaucoup plus, aussi bien pour les grands nombres premiers et de facteurs.

Vous ne devriez pas en boucle jusqu'à la racine carrée du nombre! Il peut être bon de temps en temps, mais pas toujours!

Plus grand facteur premier de 10 est 5, ce qui est plus grand que la sqrt(10) (3.16, aprox).

Plus grand facteur premier de 33 est de 11, ce qui est plus grand que la sqrt(33) (5.5,74, aprox).

Vous êtes à la confusion ce avec la bienséance qui stipule que, si un nombre est un facteur plus grand que son sqrt, il doit avoir au moins un autre un autre facteur premier plus petit que sa racine carrée. Donc, à vous de tester si un nombre est premier, vous avez seulement besoin de tester jusqu'à sa racine carrée.

def prime(n):
    for i in range(2,n):
        if n%i==0:
            return False
    return True

def primefactors():
    m=int(input('enter the number:'))
    for i in range(2,m):
        if (prime(i)):
            if m%i==0:
                print(i)
    return print('end of it')

primefactors()

n=int(input("Enter the number"))
if n==1 :  #because the below logic doesn't work on 1
    print(n)
for i in range(2 , n+1):
    if n%i==0 :
        n1=i  #get factor
        for b in range(2,n+1): #check if it is prime
            if ((n1%b)==0) & (n1==b):
                print(n1)
            elif (n1%b)==0 or n1<b:  #if not then pass
                break

je suis sûr que c'est le pire de la logique mais c'est toutes les connaissances que j'ai dans .py
ce programme permettra d'obtenir un nombre à l'utilisateur et imprime tous les facteurs de nombres qui sont le premier comme pour le 12, il donnera à 2,3