Tôi có một danh sách Python về các yếu tố chính của một số. Làm thế nào để tôi (pythonically) tìm thấy tất cả các yếu tố?

Question

Tôi đang làm việc trên một vấn đề Dự án Euler yêu cầu hệ số của một số nguyên. Tôi có thể đưa ra một danh sách tất cả các số nguyên tố là yếu tố của một số đã cho. Định lý cơ bản về số học ngụ ý rằng tôi có thể sử dụng danh sách này để lấy được mỗi hệ số của số.

Kế hoạch hiện tại của tôi là lấy từng số trong danh sách số nguyên tố cơ bản và tăng sức mạnh cho đến khi nó không còn là hệ số nguyên để tìm số mũ tối đa cho mỗi số nguyên tố. Sau đó, tôi sẽ nhân tất cả các kết hợp có thể có của cặp số nguyên tố.

Vì vậy, ví dụ, đối với 180:

Given: prime factors of 180: [2, 3, 5] 
Find maximum exponent of each factor: 
    180/2^1 = 90 
    180/2^2 = 45 
    180/2^3 = 22.5 - not an integer, so 2 is the maximum exponent of 2. 

    180/3^1 = 60 
    180/3^2 = 20 
    180/3^3 = 6.6 - not an integer, so 2 is the maximum exponent of 3. 

    180/5^1 = 36 
    180/5^2 = 7.2 - not an integer, so 1 is the maximum exponent of 5. 

Tiếp theo, làm mọi sự kết hợp của những lên đến số mũ tối đa để có được những yếu tố:

2^0 * 3^0 * 5^0 = 1 
    2^1 * 3^0 * 5^0 = 2 
    2^2 * 3^0 * 5^0 = 4 
    2^0 * 3^1 * 5^0 = 3 
    2^1 * 3^1 * 5^0 = 6 
    2^2 * 3^1 * 5^0 = 12 
    2^0 * 3^2 * 5^0 = 9 
    2^1 * 3^2 * 5^0 = 18 
    2^2 * 3^2 * 5^0 = 36 
    2^0 * 3^0 * 5^1 = 5 
    2^1 * 3^0 * 5^1 = 10 
    2^2 * 3^0 * 5^1 = 20 
    2^0 * 3^1 * 5^1 = 15 
    2^1 * 3^1 * 5^1 = 30 
    2^2 * 3^1 * 5^1 = 60 
    2^0 * 3^2 * 5^1 = 45 
    2^1 * 3^2 * 5^1 = 90 
    2^2 * 3^2 * 5^1 = 180 

Vì vậy, danh sách các yếu tố = [1 , 2, 3, 4, 5, 6, 9, 10, 12, 15, 18, 20, 30, 36, 45, 60, 90, 180]

Đây là mã tôi có cho đến nay. Hai vấn đề: Thứ nhất, tôi không nghĩ rằng nó là rất Pythonic cả. Tôi muốn khắc phục điều đó. Thứ hai, tôi thực sự không có một cách Pythonic để làm bước thứ hai tổ hợp. Trong sự xấu hổ, tôi đã tha cho bạn khỏi các vòng lặp vô lý.

n là số chúng tôi muốn tính. listOfAllPrimes là một danh sách được tính toán trước của các số nguyên tố lên đến 10 triệu.

def getListOfFactors(n, listOfAllPrimes): 
    maxFactor = int(math.sqrt(n)) + 1 
    eligiblePrimes = filter(lambda x: x <= maxFactor, listOfAllPrimes) 
    listOfBasePrimes = filter(lambda x: n % x ==0, eligiblePrimes) 

    listOfExponents = [] #(do I have to do this?) 
    for x in listOfBasePrimes: 
     y = 1 
     while (x**(y+1)) % n == 0: 
      y += 1 
     listOfExponents.append(y) 

Answer 1

Thay vì một danh sách các số mũ, xem xét việc chỉ lặp lại mỗi thừa số nguyên tố bằng số lần nó là một yếu tố. Sau đó, làm việc theo kết quả primefactors danh sách-với-lặp lại, itertools.combinations chỉ là những gì bạn cần - bạn sẽ chỉ cần kết hợp chiều dài từ 2 đến len(primefactors) - 1 mục được bao gồm (kết hợp của chỉ một là các yếu tố chính, của tất cả của họ sẽ là số ban đầu - nếu bạn muốn những người quá, chỉ cần sử dụng range(1, len(primefactors) + 1) thay vì range(2, len(primefactors)) mà đề nghị chính của tôi sẽ sử dụng).

Sẽ có lặp đi lặp lại trong các kết quả (ví dụ, 6 sẽ xuất hiện hai lần như một yếu tố của 12, từ những năm primefactors sau sẽ [2, 2, 3]) và họ có thể đương nhiên bị loại bỏ bằng những cách thông thường (tức là sorted(set(results)) ví dụ) .

Để tính primefactors cho listOfAllPrimes, hãy xem xét ví dụ:

def getprimefactors(n): 
    primefactors = [] 
    primeind = 0 
    p = listOfAllPrimes[primeind] 
    while p <= n: 
     if n % p == 0: 
      primefactors.append(p) 
      n //= p 
     else: 
      primeind += 1 
      p = listOfAllPrimes[primeind] 
    return primefactors 

Answer 2

Bạn có thể sử dụng itertools.combinations() để có được tất cả các kết hợp có thể có của các yếu tố khi bạn đã có danh sách các số nguyên tố lặp đi lặp lại-, chẳng hạn như [2, 2, 3, 3, 5] cho 180. Sau đó, chỉ cần nhân các thành phần từ mỗi kết hợp sẽ giúp bạn có được một yếu tố.

Answer 3

Dưới đây là một giải pháp đơn giản và hiệu quả cho vấn đề ban đầu:

def getDivisors(n): 
    divisors = [] 
    d = 1 
    while d*d < n: 
     if n % d == 0: 
      divisors.append(d) 
      divisors.append(n/d); 
     d += 1 
    if d*d == n: 
     divisors.append(d) 
    return divisors 

Danh sách đầu ra là không được phân loại. Bạn có thể làm cho nó thêm "pythonic" nếu bạn muốn, bất cứ điều gì có nghĩa là.

Answer 4

Tại sao bạn bắt đầu giải pháp của mình từ tập hợp các yếu tố chính? khi bạn tích lũy một số, bạn có thể dễ dàng có được tất cả các thừa số nguyên tố của nó (lặp lại) và từ chúng thành số mũ cho mỗi thừa số. Với điều này trong tâm trí, bạn có thể viết này:

import itertools 
prime_factors = get_prime_factors(180) 
# 2, 2, 3, 3, 5 
factorization = [(f, len(list(fs))) for (f, fs) in itertools.groupby(prime_factors)] 
# [(2, 2), (3, 2), (5, 1)] 
values = [[(factor**e) for e in range(exp+1)] for (factor, exp) in factorization] 
# [[1, 2, 4], [1, 3, 9], [1, 5]] 
print sorted(product(xs) for xs in itertools.product(*values)) 
# [1, 2, 3, 4, 5, 6, 9, 10, 12, 15, 18, 20, 30, 36, 45, 60, 90, 180] 

get_prime_factors và product không được thực hiện ở đây, nhưng bạn sẽ có được ý tưởng (cả hai đều khá đơn giản để viết)

IMHO, là vấn đề toán học, Euler vấn đề có thể được giải quyết tốt bằng cách sử dụng chức năng thay vì phong cách bắt buộc (mặc dù tôi thừa nhận rằng một số giải pháp có thể không đi ra như pythonic như mong muốn).

Answer 5

Với một vài tính năng Python mát:

def factors(num): 
    for p in primes: 
     if num==1: break # stop when num is 1 
     while True: # these factors may be repeated 
      new, rest = divmod(num, p) # does div and mod at once 
      if rest==0: # its divisible 
       yield p # current prime is factor 
       num = new # continue with the div'd number 
      else: 
       break # no factor so break from the while 


print list(factors(2*2*3*3*5*7*11*11*13)) # [2, 2, 3, 3, 5, 7, 11, 11, 13] ofc 

Answer 6

Một tất cả trong một giải pháp; tức là không cần danh sách các yếu tố chính hiện có.

#!/usr/bin/python3 -O 

from primegen import erat3 as generate_primes # see Note[1] 
import operator as op, functools as ft, itertools as it 

def all_factors(number): 
    prime_powers= [] 

    for prime in generate_primes(): # for prime in listOfAllPrimes 
     if prime > number: break 

     this_prime_powers= [1] 
     new_number, modulo= divmod(number, prime) 

     while not modulo: 
      number= new_number 
      this_prime_powers.append(this_prime_powers[-1] * prime) 
      new_number, modulo= divmod(number, prime) 

     if len(this_prime_powers) > 1: 
      prime_powers.append(this_prime_powers) 

    # at this point: 
    # if number was 360, prime_powers is [[1, 2, 4, 8], [1, 3, 9], [1, 5]] 
    # if number was 210, prime_powers is [[1, 2], [1, 3], [1, 5], [1, 7]] 

    return sorted(
     ft.reduce(op.mul, combination, 1) 
     for combination in it.product(*prime_powers)) 

if __name__ == "__main__": 
    def num_result(number): 
     return number, all_factors(number) 
    print(num_result(360)) 
    print(num_result(210)) 
    print(num_result(7)) 

Lưu ý [1]: Như một máy phát điện số nguyên tố, bạn có thể chọn một từ How to implement an efficient infinite generator of prime numbers in Python? hoặc sử dụng riêng của bạn (ví dụ bạn listOfAllPrimes).

Điều này tạo danh sách yếu tố đầy đủ, tức là bao gồm cả 1 và chính đối số number. Nếu bạn muốn bỏ qua những điều này, bạn có thể sử dụng all_factors(number)[1:-1].

$ allfactors.py 
(360, [1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18, 20, 24, 30, 36, 40, 45, 60, 72, 90, 120, 180, 360]) 
(210, [1, 2, 3, 5, 6, 7, 10, 14, 15, 21, 30, 35, 42, 70, 105, 210]) 
(7, [1, 7])