How to Find Factors of a Number Using the Simplest Python Method

How to find factors of a number using the simplest python method

def factors(n):
a = []
x = 2
while x * x <= n :
if n % x == 0:
a.append(x)
n /= x
else: x += 1
if n > 1: a.append(n)
return a

all downvoted as quickly as possible.

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

from functools import reduce

def factors(n):
return set(reduce(list.__add__,
([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))

This will return all of the factors, very quickly, of a number n.

Why square root as the upper limit?

sqrt(x) * sqrt(x) = x. So if the two factors are the same, they're both the square root. If you make one factor bigger, you have to make the other factor smaller. This means that one of the two will always be less than or equal to sqrt(x), so you only have to search up to that point to find one of the two matching factors. You can then use x / fac1 to get fac2.

The reduce(list.__add__, ...) is taking the little lists of [fac1, fac2] and joining them together in one long list.

The [i, n/i] for i in range(1, int(sqrt(n)) + 1) if n % i == 0 returns a pair of factors if the remainder when you divide n by the smaller one is zero (it doesn't need to check the larger one too; it just gets that by dividing n by the smaller one.)

The set(...) on the outside is getting rid of duplicates, which only happens for perfect squares. For n = 4, this will return 2 twice, so set gets rid of one of them.

Faster Way To Find Factors of n only using the math library

EDIT: Just like @John Coleman said in the comment of this solution, it's better to obtain the factors while you're calculating the primes, so you can avoid extra work in case you finish factorizing the number before the sieve is finished. The updated code would be:

def factors(number):
n=int(number**.5)+1
x=number
divisors=[]
era =[1] * n
primes=[]
for p in range(2, n):
if era[p]:
primes.append(p)
while x%p==0:
x//=p
divisors.append(p)
for i in range(p*p, n, p):
era[i] = False
if x!=1:
divisors.append(x)
return divisors

OG Solution:

Get the prime factors between 2 and sqrt(n) with the Erathostenes Sieve and after it, check which ones are divisors of n. That will reduce hugely the running time of your code.

The Erathostenes sieve doesn't use more than lists, operations %,>=,<= and booleans.

Here's a shorter implementation than the one in the link I shared you:

def factors(number):
n=int(number**.5)+1
era =[1] * n
primes=[]
for p in range(2, n):
if era[p]:
primes.append(p)
for i in range(p*p, n, p):
era[i] = False
divisors=[]
x=number
for i in primes:
while x%i==0:
x//=i
divisors.append(i)
if x!=1:
divisors.append(x)
return divisors

Python; finding the factors of a number code using a dictionary. Why doesn't this work?

There are at least two problems with your approach:

  1. You're setting factors[number] = [] every time you find a factor. That means every time you find a factor, you erase the previously found one. Since on the last iteration of the loop, i will equal number, and number % number == 0, your list of factors will always contain only number itself.

  2. You're not returning anything from your function.

The minimal change I see to make your function work is to move factors[number] = [] outside the inner loop, and to return the factors dictionary when you're done:

def factors(start, end):

factors = {}

for number in range(start, end + 1):
factors[number] = []
for i in range(2, number+1):
if number % i == 0:
factors[number].append(i)
return factors

List all factors of number

You can refer this code:

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

values = ""
for v in factor_values:
values += str(v) + " "

return values

The function will return 1 2 3 6

How to find the common factors of 2 numbers

Apparently GCD is there already, so the other answer could be modified as

from fractions import gcd
def cf(num1,num2):
n=[]
g=gcd(num1, num2)
for i in range(1, g+1):
if g%i==0:
n.append(i)
return n

print(cf(int(input("a:")),int(input("b:"))))

Then of course you can use the "trick" from prime-tests, and loop until the square root of the number only, as divisors come in pairs:

from fractions import gcd
from math import sqrt
def cf(num1,num2):
n=[]
g=gcd(num1, num2)
for i in range(1, int(sqrt(g))+1):
if g%i==0:
n.append(i)
if g!=i*i:
n.append(int(g/i))
return n

print(cf(int(input("a:")),int(input("b:"))))

Function to find the factors of a negative number

def factorspos(x):
x = int(x)
factorspos = []
print("The factors of",x,"are:")
if x > 0: # if input is postive
for i in range(1,x+1):
if x % i == 0:
factorspos.append(i)
print(i)
return factorspos
elif x < 0: #if input is negative
for i in range(x,0):
if x % i == 0:
factorspos.append(i)
print(i)
return factorspos


print(factorspos(12)) #outputs [1, 2, 3, 4, 6, 12]
print(factorspos(-12)) #outputs [-12, -6, -4, -3, -2, -1]

You were actually really close to fixing your issue. I took the liberty of adding an extra function to what you had. Basically I added a condiction checker to see if the input x is positive or negative, the the function did two different things. What they do was what you provided, but cleaned up.

Things to note range() starts from one the first number inclusive, and ends one number short of the second parameter. range(1,10) will give you 1 to 9. So that's why if you look, the negative section the range goes from x to 0 since that will say x to -1. In the positive section it will go from 1 to x+1 since +1 insures we include our input. The rest you know about since, well you wrote it; if not feel free to ask questions.



Related Topics



Leave a reply



Submit