Наименьшее общее кратное 2 чисел на простые множители числа - PullRequest
Новая
       28

Наименьшее общее кратное 2 чисел на простые множители числа

0 голосов
/ 18 сентября 2018

В этом коде я пытаюсь получить простые факторы для простого метода, чтобы найти LCM. затем я пытаюсь сохранить его с помощью счетчика, но не могу разделить ключ и значения для правильного метода. Я застрял у стойки, пожалуйста, кто-нибудь может мне помочь? 

from collections import Counter

def q2_factor_lcm(a, b): #function for lcm
    fa = factor_list(a)  #factor list for a
    fb = factor_list(b) #factorlist for b
    c = Counter(fa) #variables to save counter for a
    d = Counter(fb) #variables to save counter for b
    r = c | d

    r.keys()
    for key, value in sorted(r.items()): # for loop for getting counter                                                              subtraction
        l = pow(key, value)
        result = []              # I am getting confused what to do now
        for item in l:
            result.append(l)
    return result #will return result

def factor_list(n): # it is to generate prime numbers 
    factors = [] # to save list
    iprimes = iter( primes_list(n) ) # loop
    while n > 1:
        p = next(iprimes)
        while n % p == 0: # python calculation
            n = n // p
            factors.append(p)
    return factors # it will return factors

1 Ответ

0 голосов
/ 18 сентября 2018

Во-первых, этот метод не очень эффективен, чтобы найти lcm. Поскольку есть хороший и чистый алгоритм для поиска gcd, проще получить lcm a и b на lcm = a * b / gcd(a,b) (*).

Во-вторых, никогда использовать pow с целочисленными значениями. Известно, что арифметика с плавающей запятой ломаная не точна.

Теперь на ваш вопрос. Операция обновления на 2 счетчиках не то, что вы хотите: вы теряете одно из значений, когда ключ присутствует в обоих диктовках. Вместо этого следует использовать объединение наборов ключей, а затем использовать максимум обоих значений (несуществующий ключ рассматривается как значение 0 для показателя степени): 

...
# use a true dict to be able to later use the get method with a default
c = dict(Counter(fa)) #variables to save counter for a
d = dict(Counter(fb)) #variables to save counter for b

result = []
for key in sorted(set(c.keys()).union(set(d.keys()))):
    exp = max(c.get(key, 0), d.get(key, 0))
    for i in range(exp):
        result.append(key)
return result

(*) Хитрость в том, что когда a> b, GCD (a, b) является GCD (b, mod (a, b)). В Python это дает сразу: 

def gcd(a, b):
    if b > a:
        return gcd(b, a)
    if b == 1:
        return b
    m = a % b
    return b if m == 0 else gcd(b, m)

def lcm(a,b):
    return a * b / gcd(a,b)
...