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:
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 equalnumber
, andnumber % number == 0
, your list of factors will always contain onlynumber
itself.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
String Concatenate Typeerror: Can Only Concatenate Str (Not "Int") to Str"
Python Command Not Working in Command Prompt
Add Excel File Attachment When Sending Python Email
How to Smooth a Curve in the Right Way
Import a File from a Subdirectory
Index Out of Bounds Error:Python
How to Calculate a Gaussian Kernel Matrix Efficiently in Numpy
Append Dataframes Together in for Loop
How to Extract All Upper from a String - Python
How to Hide Tkinter Python Gui
How to Drop Rows of Pandas Dataframe Whose Value in a Certain Column Is Nan
How to Display Index During List Iteration With Django
How to Select Percentage of Rows in Pandas Dataframe
Multiprocessing: How to Use Pool.Map on a Function Defined in a Class