Сколько факторов в целое число

Question

Мне нужно создать функцию, которая вычисляет, сколько факторов имеет целое число. Например, когда я вызываю factor(10), функция должна сказать, что она имеет 4 фактора (1, 2, 5, 10). Так с чего бы мне начать? Нужно ли ставить?

Answer 1

Оператор % (модуль) дает остаток от деления. Если этот остаток равен 0, то второе кратное является множителем второго. Поэтому просто переберите все числа от 1 до n и проверьте, являются ли они факторами; если это так, добавьте их в список с помощью append:

def factors(n):
    result = []

    for i in range(1, n + 1):
        if n % i == 0:
            result.append(i)

    return result

Вот демо.

Или, более кратко, используя лямбды:

def factors(n):
    return filter(lambda i: n % i == 0, range(1, n + 1))

Вот демонстрация.

Answer 2

Я использую этот код.Он проверяет до sqrt (n), пропуская все кратные 2 и 3. Не так медленно ... Этот возвращает только основные факторы, а не композиты.

def factorize(n1):
    if n1==0: return []
    if n1==1: return [1]
    n=n1
    b=[]
    while n % 2 ==0 : b.append(2);n/=2
    while n % 3 ==0 : b.append(3);n/=3
    i=5
    inc=2
    while i*i<=n:
     while n % i ==0 : b.append(i); n/=i
     i+=inc
     inc=6-inc
    if n<>1:b.append(n) 
    return b 

С целым числом из 16 цифр:

>>> 
1234567890123456 [2, 2, 2, 2, 2, 2, 3, 7, 7, 301319, 435503] in  0.36825485272  seconds
>>> 

Answer 3

Я думаю, что стоило бы измерить производительность решения, которое делает модуль только по первым sqrt(n) числам.

def factors(n):
    sqrt = int(n ** .5)
    half_factors = [i for i in range(1, sqrt + 1) if n % i == 0]
    return half_factors + [n // i for i in half_factors[n%sqrt == 0::-1]]

Быстрый тест:

>>> factors(16)
[1, 2, 4, 8, 16]
>>> factors(20)
[1, 2, 4, 10, 20]

Примечание: Измените range на xrange, если вы находитесь в Python 2, но сохраните //, который явно вызывает деление на этаж.

Answer 4

Для небольших чисел:

def factors(n):
    return [f for f in range(1,n+1) if n%f==0]

Для повышения производительности, если вас просто интересует количество простых чисел, вы можете найти простую факторизацию.См. Статью в Википедии, чтобы найти алгоритмы для этого.Если у вас есть основная факторизация, обратите внимание, что каждое число может быть либо включено, либо исключено.Например 72 == 2^3 * 3^2.Мы можем иметь либо 0, либо 1, либо 2, либо 3 3 с и 0 or 1 or 2 3 с для 4 * 3 = 12 возможных комбинаций.(Коэффициент 1 соответствует вариантам выбора 0 из каждого набора простых факторов, а само число соответствует максимально большому выбору из каждого набора простых факторов.)

from functools import reduce  # needed in python3
from operators import *

def factors(n):
    primeFactors = prime_factorization_algorithm(n)
    # e.g. algorithm(72) == Counter({2:3, 3:2})

    return reduce(mul, (count+1 for factor,count in primeFactors.items()))

Answer 5

import math
test = 3
p = [2]
#List of primes
correct = 0
limit = 100"""Set this to square root of number you are testing"""

while True:
    if test <= limit:
            if not test % p[correct - 1] == 0:
                correct = correct + 1
                if p[correct - 1] > test**0.5:
                    length = length + 1
                    correct = 0
                    p.append(test)
            else:
                test = test + 2
                correct = 0
    else:

        break
bt = int(input("Find factors of which number? "))
btt = bt
test_digit = 0
factors = []
num_factors = 1
factor_amount = 1
while True:
    if p[test_digit] < bt**0.5:
        if bt%p[test_digit] == 0:
            factors.append(p[test_digit])
            bt = bt / p[test_digit]
            factor_amount = factor_amount + 1
        else:
            test_digit = test_digit + 1
            if factor_amount > 1:
                num_factors = factor_amount * num_factors
                factor_amount = 1
    else:
        if bt > 1:
            factors.append(math.floor(bt))
            num_factors = num_factors * 2
        break
print(btt,"has",num_factors,"which are",factors)
    else:
        break

Это должно найти, какие главные факторы и сколько уникальных факторов у него есть.

Answer 6

Вам нужно только разделить от 2 - sqrt (число), чтобы определить, является ли оно составным.Таким образом, когда вы делаете это, всякий раз, когда число делится, вы получаете два его фактора, скажем, x и y, такие что x * y = число.Теперь вы можете написать рекурсивную функцию факторов, которая рекурсивно находит факторы числа, x и y и, наконец, возвращает набор факторов без дубликатов (вам нужно найти способ удалить их).