python - problems - Prime factorización-lista

find the prime factorization

Question

Estoy intentando implementar una función primeFac() que toma como entrada un entero positivo n devuelve una lista que contiene todos los números en la factorización prima de n .

He llegado hasta aquí, pero creo que sería mejor usar la recursión aquí, no estoy seguro de cómo crear un código recursivo aquí, ¿cuál sería el caso base? para empezar.

Mi código:

def primes(n):
    primfac = []
    d = 2
    while (n > 1):
         if n%d==0:
             primfac.append(d)
    # how do I continue from here... ?

Answer 1

Aquí está mi versión de factorización por división de prueba, que incorpora la optimización de dividir solo por dos y los enteros impares propuestos por Daniel Fischer:

def factors(n):
    f, fs = 3, []
    while n % 2 == 0:
        fs.append(2)
        n /= 2
    while f * f <= n:
        while n % f == 0:
            fs.append(f)
            n /= f
        f += 2
    if n > 1: fs.append(n)
    return fs

Una mejora en la división de prueba en dos y en los números impares es la factorización de rueda , que utiliza un conjunto cíclico de espacios entre potenciales números primos para reducir en gran medida el número de divisiones de prueba. Aquí usamos una rueda 2,3,5:

def factors(n):
    gaps = [1,2,2,4,2,4,2,4,6,2,6]
    length, cycle = 11, 3
    f, fs, nxt = 2, [], 0
    while f * f <= n:
        while n % f == 0:
            fs.append(f)
            n /= f
        f += gaps[nxt]
        nxt += 1
        if nxt == length:
            nxt = cycle
    if n > 1: fs.append(n)
    return fs

Por lo tanto, los print factors(13290059) generarán [3119, 4261] . Las ruedas de factoring tienen la misma complejidad de tiempo O (sqrt (n)) que la división de prueba normal, pero serán dos o tres veces más rápidas en la práctica.

He trabajado mucho con números primos en mi blog . Por favor, siéntase libre de visitar y estudiar.

Answer 2

El módulo Primefac tiene factorizaciones con todas las técnicas sofisticadas que los matemáticos han desarrollado a lo largo de los siglos:

#!python

import primefac
import sys

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

Answer 3

Esta es una solución basada en la comprensión, podría ser lo más cercano que pueda llegar a una solución recursiva en Python mientras sea posible usarla para números grandes.

Puedes obtener los divisores adecuados con una línea:

divisors = [ d for d in xrange(2,int(math.sqrt(n))) if n % d == 0 ]

entonces podemos probar que un número en divisores sea primo:

def isprime(d): return all( d % od != 0 for od in divisors if od != d )

que prueba que ningún otro divisor se divide d.

Entonces podemos filtrar los divisores primos:

prime_divisors = [ d for d in divisors if isprime(d) ]

Por supuesto, se puede combinar en una sola función:

def primes(n):
    divisors = [ d for d in range(2,n//2+1) if n % d == 0 ]
    return [ d for d in divisors if /
             all( d % od != 0 for od in divisors if od != d ) ]

Aquí, el / está ahí para romper la línea sin jugar con la sangría de Python.

Answer 4

Este es el código que hice. Funciona bien para números con números primos pequeños, pero lleva un tiempo para números con números primos de millones.

def pfactor(num):
div = 2
pflist = []
while div <= num:
    if num % div == 0:
        pflist.append(div)
        num /= div
    else:
        div += 1
# The stuff afterwards is just to convert the list of primes into an expression
pfex = ''''
for item in list(set(pflist)):
    pfex += str(item) + ''^'' + str(pflist.count(item)) + '' * ''
pfex = pfex[0:-3]
return pfex

Answer 5

He modificado la respuesta de @user448810 para usar iteradores de itertools (y python3.4, pero debería ser back-portable). La solución es aproximadamente un 15% más rápida.

import itertools

def factors(n):
    f = 2
    increments = itertools.chain([1,2,2], itertools.cycle([4,2,4,2,4,6,2,6]))
    for incr in increments:
        if f*f > n:
            break
        while n % f == 0:
            yield f
            n //= f
        f += incr
    if n > 1:
        yield n

Tenga en cuenta que esto devuelve un iterable, no una lista. Envuélvalo en la lista () si eso es lo que quiere.

Answer 6

La mayoría de las respuestas hacen que las cosas sean demasiado complejas. Podemos hacer esto

def prime_factors(n):
    num = []

    #add 2 to list or prime factors and remove all even numbers(like sieve of ertosthenes)
    while(n%2 == 0):
        num.append(2)
        n /= 2

    #divide by odd numbers and remove all of their multiples increment by 2 if no perfectlly devides add it
    for i in xrange(3, int(sqrt(n))+1, 2):
        while (n%i == 0):
            num.append(i)
            n /= i

    #if no is > 2 i.e no is a prime number that is only divisible by itself add it
    if n>2:
        num.append(n)

    print (num)

Algoritmo de GeeksforGeeks

Answer 7

La mayoría de las soluciones anteriores aparecen algo incompletas. Una factorización prima repetiría cada factor primo del número (eg 9 = [3 3]) .

Además, las soluciones anteriores podrían escribirse como funciones perezosas para la conveniencia de la implementación.

El uso del sieve Of Eratosthenes para encontrar primos para probar es óptimo, pero; la implementación anterior utilizó más memoria de la necesaria.

No estoy seguro de si / cómo la "wheel factorization" sería superior a la aplicación de factores primos, para las pruebas de división de n.

Si bien estas soluciones son realmente útiles, sugeriría las siguientes dos funciones:

Función-1:

def primes(n):
    if n < 2: return
    yield 2
    plist = [2]
    for i in range(3,n):
        test = True
        for j in plist:
            if j>n**0.5:
                break
            if i%j==0:
                test = False
                break
        if test:
            plist.append(i)
            yield i

Función-2:

def pfactors(n):
    for p in primes(n):
        while n%p==0:
            yield p
            n=n//p
            if n==1: return

list(pfactors(99999))
[3, 3, 41, 271]

3*3*41*271
99999

list(pfactors(13290059))
[3119, 4261]

3119*4261
13290059

Answer 8

Manera simple de obtener la solución deseada

def Factor(n):
    d = 2
    factors = []
    while n >= d*d:
        if n % d == 0:
            n//=d
            # print(d,end = " ")
            factors.append(d)
        else:
            d = d+1
    if n>1:
        # print(int(n))
        factors.append(n)
    return factors

Answer 9

Me gustaría compartir mi código para encontrar los factores primos del número dado por el usuario:

a = int(input("Enter a number: "))

def prime(a):
    b = list()
    i = 1
    while i<=a:
        if a%i ==0 and i!=1 and i!=a:
            b.append(i)
        i+=1
    return b

c = list()
for x in prime(a):
    if len(prime(x)) == 0:
        c.append(x)

print(c)

Answer 10

Puedes usar tamiz de Eratóstenes para generar todos los primos hasta (n/2) + 1 y luego utilizar una lista de comprensión para obtener todos los factores primos:

def rwh_primes2(n):
    # http://.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
    """ Input n>=6, Returns a list of primes, 2 <= p < n """
    correction = (n%6>1)
    n = {0:n,1:n-1,2:n+4,3:n+3,4:n+2,5:n+1}[n%6]
    sieve = [True] * (n/3)
    sieve[0] = False
    for i in xrange(int(n**0.5)/3+1):
      if sieve[i]:
        k=3*i+1|1
        sieve[      ((k*k)/3)      ::2*k]=[False]*((n/6-(k*k)/6-1)/k+1)
        sieve[(k*k+4*k-2*k*(i&1))/3::2*k]=[False]*((n/6-(k*k+4*k-2*k*(i&1))/6-1)/k+1)
    return [2,3] + [3*i+1|1 for i in xrange(1,n/3-correction) if sieve[i]]

def primeFacs(n):
    primes = rwh_primes2((n/2)+1)
    return [x for x in primes if n%x == 0]

print primeFacs(99999)
#[3, 41, 271]

Answer 11

Una simple división de prueba:

def primes(n):
    primfac = []
    d = 2
    while d*d <= n:
        while (n % d) == 0:
            primfac.append(d)  # supposing you want multiple factors repeated
            n //= d
        d += 1
    if n > 1:
       primfac.append(n)
    return primfac

con complejidad O(sqrt(n)) (peor caso). Puede mejorarlo fácilmente mediante el revestimiento especial 2 y el bucle solo sobre el d impar (o mayúsculas especiales más pequeñas y con bucles sobre menos divisores posibles).

Answer 12

factores primos de un número:

def primefactors(x):
    factorlist=[]
    loop=2
    while loop<=x:
        if x%loop==0:
            x//=loop
            factorlist.append(loop)
        else:
            loop+=1
    return factorlist

x = int(input())
alist=primefactors(x)
print(alist)

Obtendrás la lista. Si desea obtener los pares de factores primos de un número, intente esto: http://pythonplanet.blogspot.in/2015/09/list-of-all-unique-pairs-of-prime.html

Answer 13

    from sets import Set
    # this function generates all the possible factors of a required number x
    def factors_mult(X):
        L = []
        [L.append(i) for i in range(2,X) if X % i == 0]
        return L

    # this function generates list containing prime numbers upto the required number x 
    def prime_range(X):
        l = [2]
        for i in range(3,X+1):
            for j in range(2,i):
               if i % j == 0:
               break
            else:    
               l.append(i)
        return l

    # This function computes the intersection of the two lists by invoking Set from the sets module
    def prime_factors(X):
        y = Set(prime_range(X))
        z = Set(factors_mult(X))
        k = list(y & z)
        k = sorted(k)

        print "The prime factors of " + str(X) + " is ", k

    # for eg
    prime_factors(356)

Answer 14

def factorize(n):
  for f in range(2,n//2+1):
    while n%f == 0:
      n //= f
      yield f

Es lento pero muerto simple. Si desea crear una utilidad de línea de comandos, podría hacer lo siguiente:

import sys
[print(i) for i in factorize(int(sys.argv[1]))]

Answer 15

def get_prime_factors(number):
    """
    Return prime factor list for a given number
        number - an integer number
        Example: get_prime_factors(8) --> [2, 2, 2].
    """
    if number == 1:
        return []

    # We have to begin with 2 instead of 1 or 0
    # to avoid the calls infinite or the division by 0
    for i in xrange(2, number):
        # Get remainder and quotient
        rd, qt = divmod(number, i)
        if not qt: # if equal to zero
            return [i] + get_prime_factors(rd)

    return [number]

Answer 16

def prime_factors(num, dd=2):
    while dd <= num and num>1:
        if num % dd == 0:
            num //= dd
            yield dd
        dd +=1

Muchas de las respuestas anteriores fallan en primos pequeños, por ejemplo, 3, 5 y 7. Lo anterior es breve y lo suficientemente rápido para el uso normal.

lista de impresión (prime_factors (3))

[3]