What is the most efficient way of finding all the factors of a number in Python?

For n up to 10**16 (maybe even a bit more), here is a fast pure Python 3.6 solution,

from itertools import compress

def primes(n):
    """ Returns  a list of primes < n for n > 2 """
    sieve = bytearray([True]) * (n//2)
    for i in range(3,int(n**0.5)+1,2):
        if sieve[i//2]:
            sieve[i*i//2::i] = bytearray((n-i*i-1)//(2*i)+1)
    return [2,*compress(range(3,n,2), sieve[1:])]

def factorization(n):
    """ Returns a list of the prime factorization of n """
    pf = []
    for p in primeslist:
      if p*p > n : break
      count = 0
      while not n % p:
        n //= p
        count += 1
      if count > 0: pf.append((p, count))
    if n > 1: pf.append((n, 1))
    return pf

def divisors(n):
    """ Returns an unsorted list of the divisors of n """
    divs = [1]
    for p, e in factorization(n):
        divs += [x*p**k for k in range(1,e+1) for x in divs]
    return divs

n = 600851475143
primeslist = primes(int(n**0.5)+1) 
print(divisors(n))

The simplest way of finding factors of a number:

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

Here is another alternate without reduce that performs well with large numbers. It uses sum to flatten the list.

def factors(n):
    return set(sum([[i, n//i] for i in xrange(1, int(n**0.5)+1) if not n%i], []))

If you don't want to use any libraries, then I think this is the easiest way to do it:

def factors(n):
    l = [] # empty list
    # appending the factors in the list
    for i in range(1,n+1):
        if n%i==0:
            l.append(i)
    return l

I found a simple solution using cypari library in python. Here's a link!

import cypari
def get_divisors(n):
   divisors = cypari.pari('divisors({})'.format(n))
   return divisors
print(get_divisors(24))

output

[1, 2, 3, 4, 6, 8, 12, 24]

I was pretty surprised when I saw this question that no one used numpy even when numpy is way faster than python loops. By implementing @agf's solution with numpy and it turned out at average 8x faster. I belive that if you implemented some of the other solutions in numpy you could get amazing times.

Here is my function:

import numpy as np
def b(n):
    r = np.arange(1, int(n ** 0.5) + 1)
    x = r[np.mod(n, r) == 0]
    return set(np.concatenate((x, n / x), axis=None))   

Notice that the numbers of the x-axis are not the input to the functions. The input to the functions is 2 to the the number on the x-axis minus 1. So where ten is the input would be 2**10-1 = 1023

your max factor is not more than your number, so, let's say

def factors(n):
    factors = []
    for i in range(1, n//2+1):
        if n % i == 0:
            factors.append (i)
    factors.append(n)

    return factors

voilá!

 import math

    '''
    I applied finding prime factorization to solve this. (Trial Division)
    It's not complicated
    '''


    def generate_factors(n):
        lower_bound_check = int(math.sqrt(n))  # determine lowest bound divisor range [16 = 4]
        factors = set()  # store factors
        for divisors in range(1, lower_bound_check + 1):  # loop [1 .. 4]
            if n % divisors == 0:
                factors.add(divisors)  # lower bound divisor is found 16 [ 1, 2, 4]
                factors.add(n // divisors)  # get upper divisor from lower [ 16 / 1 = 16, 16 / 2 = 8, 16 / 4 = 4]
        return factors  # [1, 2, 4, 8 16]


    print(generate_factors(12)) # {1, 2, 3, 4, 6, 12} -> pycharm output

 Pierre Vriens hopefully this makes more sense. this is an O(nlogn) solution. 

While the question says Python (2.7), people may be interested in this simple solution using Numpy.

import numpy as np

t=np.arange(2,n,1)
t[n%t==0]

This will not return 1 nor the number itself n. So it will return an empty array if n is prime.

loop until you find a duplicate in x or v of the tuple where x is the denominator and v is the resultant.

number=30
tuple_list=[]
for i in np.arange(1,number):
    if number%i==0:
         other=int(number/i)
         if any([(x,v) for (x,v) in tuple_list if (i==x) or (i==v)])==True:
             break
         tuple_list.append((i,other))
    
 flattened = [item for sublist in tuple_list for item in sublist]              
 print(sorted(flattened))

output

 [1, 2, 3, 5, 6, 10, 15, 30]

We can use the following lambda function,

factor = lambda x:[(ele,x/ele) for ele in range(1,x//2+1) if x%ele==0 ]

factor(10)

output: [(1, 10.0), (2, 5.0), (5, 2.0)]

This function returns all the factors of the given number in list.

Considering the number is positive integer, you may use this approach:

number = int(input("Enter a positive number to find factors: "))
factor = [num for num in range(1,number+1) if number % num == 0]
for fac in factor: print(f"{fac} is a factor of {number}")

import 'dart:math';
generateFactorsOfN(N){
  //determine lowest bound divisor range
  final lowerBoundCheck = sqrt(N).toInt();
  var factors = Set<int>(); //stores factors
  /**
   * Lets take 16:
   * 4 = sqrt(16)
   * start from 1 ...  4 inclusive
   * check mod 16 % 1 == 0?  set[1, (16 / 1)]
   * check mod 16 % 2 == 0?  set[1, (16 / 1) , 2 , (16 / 2)]
   * check mod 16 % 3 == 0?  set[1, (16 / 1) , 2 , (16 / 2)] -> unchanged
   * check mod 16 % 4 == 0?  set[1, (16 / 1) , 2 , (16 / 2), 4, (16 / 4)]
   *
   *  ******************* set is used to remove duplicate
   *  ******************* case 4 and (16 / 4) both equal to 4
   *  return factor set<int>.. this isn't ordered
   */

  for(var divisor = 1; divisor <= lowerBoundCheck; divisor++){
    if(N % divisor == 0){
      factors.add(divisor);
      factors.add(N ~/ divisor); // ~/ integer division 
    }
  }
  return factors;
}

I reckon this is the simplest way to do that:

    x = 23

    i = 1
    while i <= x:
      if x % i == 0:
        print("factor: %s"% i)
      i += 1