मेरे पास किसी संख्या के प्रमुख कारकों की पाइथन सूची है। मैं (पायथनिक रूप से) सभी कारकों को कैसे ढूंढूं?

Question

मैं एक परियोजना यूलर समस्या पर काम कर रहा हूं जिसके लिए एक पूर्णांक के कारककरण की आवश्यकता है। मैं उन सभी प्राइम्स की एक सूची के साथ आ सकता हूं जो किसी दिए गए नंबर का कारक हैं। अंकगणितीय के मौलिक प्रमेय का तात्पर्य है कि मैं इस सूची का उपयोग प्रत्येक संख्या के कारक को प्राप्त करने के लिए कर सकता हूं।

मेरे वर्तमान योजना आधार अभाज्य संख्या की सूची में प्रत्येक संख्या लेने के लिए और जब तक यह नहीं रह गया है एक पूर्णांक कारक प्रत्येक प्रधानमंत्री के लिए अधिकतम घातांक को मिल रहा है अपनी शक्ति बढ़ाने के लिए है। फिर, मैं प्राइम-एक्सपोनेंट जोड़े के हर संभव संयोजन को गुणा कर दूंगा।

उदाहरण के लिए, के लिए 180:

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:

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, 3, 4, 5, 6, 18, 20, 30, 36, 45, 60, 9 0, 180]

यहां मेरे पास अब तक का कोड है। दो समस्याएं: सबसे पहले, मुझे नहीं लगता कि यह बहुत पाइथनिक है। मैं इसे ठीक करना चाहता हूं। दूसरा, मैं वास्तव में संयोजन के दूसरे चरण को करने के लिए पाइथोनिक तरीका नहीं है। शर्म की बात है, मैंने तुम्हें हास्यास्पद सेट लूप से बचा लिया है।

एन वह संख्या है जिसे हम कारक बनाना चाहते हैं। listOfAllPrimes 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, सूची-साथ-repetitions जिसके परिणामस्वरूप itertools.combinations पर काम कर रहा सिर्फ तुम क्या जरूरत है - तुम सिर्फ लंबाई 2 len(primefactors) - 1 करने के लिए आइटम शामिल (सिर्फ एक के संयोजन प्रधानमंत्री कारक हैं के संयोजन सब की है कि आवश्यकता होगी, उनमें से मूल संख्या होगी - अगर आप उन बहुत चाहते हैं, बस range(2, len(primefactors)) जो अपने मुख्य सुझाव का प्रयोग करेंगे) के बजाय range(1, len(primefactors) + 1) का उपयोग करें।

किया जाएगा परिणामों में पुनरावृत्ति (जैसे, 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

आप itertools.combinations() का उपयोग कारकों में से सभी संभव संयोजनों पाने के लिए कर सकता है एक बार तुम बार-बार-अभाज्य संख्या की अपनी सूची, 180 के लिए इस तरह के रूप [2, 2, 3, 3, 5] मिल गया है। फिर, बस प्रत्येक संयोजन से घटकों गुणा आप एक कारक हो जाएगा।

Answer 3

यहाँ मूल समस्या के लिए एक सरल और प्रभावी समाधान है:

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 

उत्पादन सूची अवर्गीकृत है। आप इसे और अधिक "pythonic" कर सकते हैं अगर आप चाहते हैं, जो कुछ भी है कि इसका मतलब है।

Answer 4

आप अपने समाधान को प्रमुख कारकों के सेट से क्यों शुरू करते हैं? जब आप किसी संख्या को कारगर करते हैं तो आप आसानी से अपने सभी प्रमुख कारकों (दोहराए गए) और उनमें से प्रत्येक कारक के लिए एक्सपोनेंट प्राप्त कर सकते हैं। इसे ध्यान में रखते, तो आप इस लिख सकते हैं:

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 (दोनों बहुत लिखने के लिए सरल कर रहे हैं), गणित की समस्याओं को किया जा रहा है, यूलर अनिवार्य शैली के बजाय कार्यात्मक का उपयोग करके समस्याओं को अच्छी तरह हल किया जा सकता है (हालांकि मैं स्वीकार करता हूं कि कुछ समाधान वांछित के रूप में पाइथनिक के रूप में नहीं आ सकते हैं)।

Answer 5

कुछ कूलर अजगर सुविधाओं के साथ

:

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

एक एक समाधान में सभी; यानी प्रमुख कारकों की मौजूदा सूची की आवश्यकता नहीं है।

#!/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]: एक प्रमुख संख्या जनक के रूप में, आप How to implement an efficient infinite generator of prime numbers in Python? से चुन सकते हैं या अपने खुद के उपयोग कर सकते हैं (जैसे कि आपका 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])