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