# Archives for 10 Nov,2009

You are browsing the site archives by date.

## Python: Factors of a number

Project Euler often requires the factors of a number to be found, here is the function I have written for that purpose.

```def factors(n):
fact=[1,n]
check=2
rootn=sqrt(n)
while check<rootn:
if n%check==0:
fact.append(check)
fact.append(n/check)
check+=1
if rootn==check:
fact.append(check)
fact.sort()
return fact
```

As always any help in speeding up my function would be appreciated. I think it could be improved using a sieve method or by checking if its divisible by 2 first then using check+=2 starting at 3 to improve the speed of the loop by a factor of 2.

Below is a the commented version to help explain what’s going on if it’s not clear.

```def factors(n):
# 1 and n are automatically factors of n
fact=[1,n]
# starting at 2 as we have already dealt with 1
check=2
# calculate the square root of n and use this as the
# limit when checking if a number is divisible as
# factors above sqrt(n) will already be calculated as
# the inverse of a lower factor IE. finding factors of
# 100 only need go up to 10 (sqrt(100)=10) as factors
# such as 25 can be found when 5 is found to be a
# factor 100/5=25
rootn=sqrt(n)
while check<rootn:
if n%check==0:
fact.append(check)
fact.append(n/check)
check+=1
# this line checks the sqrt of the number to see if
# it is a factor putting it here prevents it appearing
# twice in the above while loop and putting it outside
# the loop should save some time.
if rootn==check:
fact.append(check)
# return an array of factors sorted into numerial order.
fact.sort()
return fact
```