لدي قائمة بيثون للعوامل الأولية لعدد. كيف يمكنني (بيثون) أن أجد كل العوامل؟

Question

أنا أعمل على مشكلة في مشروع Euler والتي تتطلب عوامل عدد صحيح. يمكنني التوصل إلى قائمة بجميع الأعداد الأولية التي هي عامل رقم معين. تعني النظرية الأساسية للحساب أنه يمكنني استخدام هذه القائمة لاستنباطها كل عامل الرقم.

تتمثل خطتي الحالية في أخذ كل رقم في قائمة الأعداد الأولية الأساسية ورفع قوتها حتى لم يعد عامل عدد صحيح للعثور على أقصى أسس لكل برايم. بعد ذلك ، سأضاعف كل مجموعة ممكنة من أزواج مكونة.

على سبيل المثال ، لمدة 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.

بعد ذلك ، افعل كل مجموعة من هذه المجموعة إلى الحد الأقصى الأساسي للحصول على العوامل:

    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

لذا فإن قائمة العوامل = [1 ، 2 ، 3 ، 4 ، 5 ، 6 ، 9 ، 10 ، 12 ، 15 ، 18 ، 20 ، 30 ، 36 ، 45 ، 60 ، 90 ، 180

هنا هو الرمز الذي لدي حتى الآن. مشكلتان: أولاً ، لا أعتقد أنه من القلق للغاية على الإطلاق. أود إصلاح ذلك. ثانياً ، أنا حقًا ليس لديك طريقة بيثون للقيام بالخطوة الثانية combinatoric. بدافع العار ، لقد نجحت في مجموعة من الحلقات المضحكة.

N هو الرقم الذي نريد عامله. ListOfallPremes هي قائمة مسبقة من الأعداد الأولية التي تصل إلى 10 ملايين.

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

بدلاً من قائمة الأسس ، فكر ببساطة التكرار كل عامل رئيسي بعدد المرات هو عامل. بعد ذلك ، العمل على النتيجة primefactors القائمة مع إعادة التهيئة ، itertools.com يفعل ما تحتاجه فقط - ستحتاج فقط إلى مجموعات من الطول 2 إلى len(primefactors) - 1 العناصر المشمولة (مجموعات واحدة فقط هي العوامل الأولية ، والعناصر الخاصة بها ستكون الرقم الأصلي - إذا كنت تريد ذلك أيضًا ، فما عليك سوى استخدامها range(1, len(primefactors) + 1) بدلا من ال range(2, len(primefactors)) الذي سيستخدمه اقتراحي الرئيسي).

سيكون هناك تكرار في النتائج (على سبيل المثال ، 6 سوف يظهر مرتين كعامل 12, ، منذ الأخير primefactors سوف يكون [2, 2, 3]) ويمكنهم بالطبع إخراجها بالطرق المعتادة (أي sorted(set(results)) فمثلا).

لحساب primefactors معطى listOfAllPrimes, ، ضع في اعتبارك على سبيل المثال:

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

لماذا تبدأ الحل الخاص بك من مجموعة العوامل الأولية؟ عندما تقوم بتوضيح رقم ، يمكنك بسهولة الحصول على جميع عوامله الأولية (المتكررة) ومنها الأسس لكل عامل. مع وضع هذا في الاعتبار ، يمكنك كتابة هذا:

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 و product لم يتم تنفيذها هنا ، لكنك تحصل على الفكرة (كلاهما سهل الكتابة)

IMHO ، كونها مشاكل رياضية ، يمكن حل مشاكل Euler بشكل جيد باستخدام وظيفي بدلاً من الأسلوب الضروري (على الرغم من أنني أقر بأن بعض الحلول قد لا تظهر على النحو المطلوب).

Answer 3

يمكنك استخدام itertools.combinations() للحصول على جميع المجموعات الممكنة من العوامل بمجرد حصولك على قائمة المهرجانات المتكررة ، مثل [2, 2, 3, 3, 5] إلى عن على 180. بعد ذلك ، ببساطة مضاعفة المكونات من كل مجموعة سوف يجعلك عاملًا.

Answer 4

مع بضع ميزات بيثون أكثر برودة:

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 5

إليك حل بسيط وفعال للمشكلة الأصلية:

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

قائمة الإخراج غير موضحة. يمكنك أن تجعلها أكثر "بيثوني" إذا أردت ، مهما كان هذا يعني.

Answer 6

كل شيء في حل واحد ؛ أي لا حاجة للحصول على قائمة موجودة من العوامل الأولية.

#!/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))

ملاحظة [1: كمولد للأرقام الأولية ، يمكنك اختيار واحد من كيفية تنفيذ مولد لا حصر له كفاءة للأعداد الأولية في بيثون؟ أو استخدم بنفسك (على سبيل المثال الخاص بك listOfAllPrimes).

هذا ينتج قائمة عوامل كاملة ، أي بما في ذلك 1 و ال number الحجة نفسها. إذا كنت تريد حذفها ، يمكنك استخدامها 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])