Найти целое число с наибольшим делителем из списка целых чисел

Question

Я пытаюсь написать функцию, чтобы найти целое число с большинством делителей из списка, но я получаю неправильный вывод. Так выглядит моя функция.

def find_my_integer_divisor(mylist): 
     def find_divisor(k): 
      count =0 
      for i in range (1,k+1): 
        if k%i==0: 
         count +=1 
      return count 
    A=mylist[0] 
    for x in mylist [0:]: 
      A=find_divisor(x) 
    return A 

Он возвращает счет последней записи в моем списке. Я знаю, что мне приходится сравнивать количество значений из каждой записи и возвращает целое число с наибольшим количеством, но не знаю, как это сделать.

Answer 1

Это должно работать:

def find_divisor(k): 
    count =0 
    for i in range (1,k+1): 
      if k%i==0: 
       count +=1 
    return count 

def find_my_integer_divisor(mylist): 
    return max(mylist, key=find_divisor) 

Answer 2

короткий ответ: используйте max с основной функцией, как ваше: find_divisor как показывать по @rofls.

Длинный ответ: в каждой итерации нужно сравнить Yours предыдущее значение с текущим значением в списке, если текущее значение имеют большее количество изменений делителей A иначе не проблема в вашем коде что вы не делаете эту проверку. Вы можете сделать что-то вроде этого

def max_divisor_count(my_list): 
    result = my_list[0] 
    for n in my_list[1:]: # start in 1 because 0 is already in result 
     if find_divisor(n) > find_divisor(result): 
      result = n 
    return result 

и это более или менее то же самое, что max с ключом функции решения делает.

Конечно, это может быть улучшено немного больше, чтобы избежать повторных вычислений, как этот

def max_divisor_count(my_list): 
    result = my_list[0] 
    div_count = find_divisor(result) 
    for n in my_list[1:]: # start in position 1 because 0 is already in result 
     if result != n: 
      temp = find_divisor(n) 
      if temp > div_count: 
       result = n 
       div_count = temp 
    return result 

Answer 3

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

Например,

288 == 2**5 * 3**2 

и число собственных факторов

(5 + 1) * (2 + 1) - 1 
    ^  ^ ^
number  number omit one case: 
of twos of threes 5 2s and 2 3s == 288, 
used in used in which is not a proper 
factor, factor factor of itself 
0..5 
(six possible 
    values) 

---

Чтобы сделать разложение на простые множители, мы должны начать с генерации простых чисел:

def primes(known_primes=[7, 11, 13, 17, 19, 23, 29]): 
    """ 
    Generate every prime number in ascending order 
    """ 
    # 2, 3, 5 wheel 
    yield from (2, 3, 5) 
    yield from known_primes 
    # The first time the generator runs, known_primes 
    # contains all primes such that 5 < p < 2 * 3 * 5 
    # After each wheel cycle the list of known primes 
    # will be added to. 
    # We need to figure out where to continue from, 
    # which is the next multiple of 30 higher than 
    # the last known_prime: 
    base = 30 * (known_primes[-1] // 30 + 1) 
    new_primes = [] 
    while True: 
     # offs is chosen so 30*i + offs cannot be a multiple of 2, 3, or 5 
     for offs in (1, 7, 11, 13, 17, 19, 23, 29): 
      k = base + offs # next prime candidate 
      for p in known_primes: 
       if not k % p: 
        # found a factor - not prime 
        break 
       elif p*p > k: 
        # no smaller prime factors - found a new prime 
        new_primes.append(k) 
        break 
     if new_primes: 
      yield from new_primes 
      known_primes.extend(new_primes) 
      new_primes = [] 
     base += 30 

, который может быть проверен l икэ

from itertools import islice 
print(list(islice(primes(), 500))) 

давая

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, ... 

Теперь, когда у нас есть простые числа, мы можем рассчитывать вхождения каждого простого фактора как так:

def prime_factor_count(n): 
    """ 
    Factorize n and yield (factor, count) for each distinct factor 
    """ 
    if n < 2: 
     return 
    else: 
     for p in primes(): 
      count = 0 
      while not n % p: 
       count += 1 
       n //= p 
      if count: 
       yield (p, count) 
       if n == 1: 
        # number is fully factored 
        break 
       elif p*p > n: 
        # no smaller prime factors - remainder is prime 
        yield (n, 1) 
        break 

, который мы можем проверить, как

print(list(prime_factor_count(288))) # => [(2, 5), (3, 2)] 

, который вы должны признать сверху, 288 == 2**5 * 3**2.Теперь мы можем

def num_proper_factors(n): 
    total_factors = 1 
    for factor, count in prime_factor_count(n): 
     total_factors *= (count + 1) 
    return total_factors - 1 

, который проверяет, как

print(num_proper_factors(288))  # => 17 

и, наконец,

def num_with_most_divisors(lst): 
    return max(lst, key=num_proper_factors) 

QED.

Answer 4

Это альтернатива выражения генератора. Примечание. Для создания 2 экземпляров генератора я использую itertools.tee. Первый - это вычисление max, второе - для подачи enumerate.

В приведенном ниже примере также показано, как вы можете использовать понимание списка, чтобы вернуть все целые числа с максимальным количеством делителей.

from itertools import tee 

lst = [1, 2, 3, 6, 8, 10, 14] 

gen1, gen2 = tee(sum(k%i==0 for i in range(1, k+1)) for k in lst) 
divmax = max(gen1) 

[lst[i] for i, j in enumerate(gen2) if j == divmax] 

# [6, 8, 10, 14]