How many factors in an integer

Question

I have to create a function that calculates how much factors an integer has. For example, when I call factor(10) the function should be able to tell me it has 4 factors (1, 2, 5, 10). So where would I start off? Would do I need to put?

Answer 1

The % (modulus) operator gives you the remainder of a division. If that remainder is 0, then the second multiple is a factor of the second. So just loop through all the numbers from 1 to n and check if they're factors; if so, add them to the list with append:

def factors(n):
    result = []

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

    return result

Here's a demo.

Or, more concisely using lambdas:

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

Here's a demo.

Answer 2

I use this code. It tests up to sqrt(n), skipping all multiples of 2 and 3. Not that slow... This one returns only the prime factors, not composites.

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 

With a 16 figures integer:

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

Answer 3

For small numbers:

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

For improved performance, if you are just interested in the number of primes, you can find the prime factorization. See the Wikipedia article to find algorithms for this. Once you have the prime factorization, notice that each number can either be included or excluded. For example 72 == 2^3 * 3^2. We can have either 0 or 1 or 2 or 3 3s, and 0 or 1 or 2 3s, for 4*3=12 possible combinations. (The factor of 1 corresponds to choices of 0 from each set of prime factors, and the number itself corresponds to maximally large choices from each set of prime factors.)

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 4

I think that it might be worth it to measure the performances of a solution that does the module only on the first sqrt(n) numbers.

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]]

Quick test:

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

Note: Change range to xrange if you are in Python 2, but keep // that explicitly call the floor division.

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

This should find what the prime factors and how many unique factors it has.

Answer 6

def num_divisors(num):
    factors = list(filter(lambda i: num%i == 0, range(1,int(num/2)+1)))
    return len(factors) + 1

The filter() function on its own does not produce a viewable array (it returns an iterator), hence why I used the list() funciton. We have returned len(factors) + 1 because to save execution time, we only found factors up to and equivalent to half of the original number. So we have missed out the number itself, hence we add 1.

Answer 7

You only need to divide from 2 - sqrt (number) to find if it is composite. So, when you do that, whenever a number divides, you get two factors of it, say x and y such that x*y =number. Now, you can write a recursive factors function that recursively finds factors of number, x and y and finally return the set of factors without duplicates(you have to find a way to remove those).