Простая факторизация с использованием понимания списка в Python - PullRequest
Новая
       18

Простая факторизация с использованием понимания списка в Python

0 голосов
/ 29 октября 2018

Как написать функцию, которая возвращает список кортежей типа (c_i, k_i) для n, такой что n = c1 ^ k1 * c2 ^ k2 * ..., ci - простое число.
Например: 12600 = 2^3 * 3^2 * 5^2 * 7^1
Желаемый вывод: [(2, 3), (3, 2), (5, 2), (7, 1)]
Я знаю, как это сделать с while, но возможно ли это сделать с использованием списка? Эффективность не требуется в этой задаче. 

# naive function 
def is_prime(n):
    return n > 1 and all(n % i != 0 for i in range(2, n))

# while version
def factorization_while(n):
    res = []
    for i in range(1, n + 1):
        if is_prime(i):
            j = 0
            while n % i == 0:
                n = n // i
                j += 1
            if j != 0:
                res.append((i, j))
    return res

# list comprehension version
def factorization(n):
    return [
        (i, j) for i in range(1, n + 1) if is_prime(i) \
        and n % i == 0 ... # add smth
    ]

1 Ответ

0 голосов
/ 29 октября 2018

Я не думаю, что это должно быть слишком сложно. На самом деле вам не нужно изменять n, чтобы найти его главные факторы, они все полностью независимы друг от друга. Так что просто переберите подходящие простые числа и найдите максимальную мощность, которая работает! 

from math import log

def prime_factors(n):
    return [(prime, max(power for power in range(1, int(log(n, prime))+1)
                              if n % prime**power == 0))
            for prime in range(2, n+1) if n % prime == 0 and isprime(prime)]

Есть несколько способов улучшить это. Вы можете использовать itertools.takewhile на бесконечном генераторе сил (например, itertools.count), поскольку, как только вы найдете первую мощность, такую, что prime**power не является фактором n, ни одна из более поздних не будет. Это позволит вам избежать звонка log.

И есть целый ряд способов эффективной итерации по простым числам (см., Например, очень простой генератор, предложенный здесь , или версии с более высокой производительностью, которые вы можете найти в ответах на несколько различных вопросов здесь, на SO).

...