# Best way to find all factors of a number?

Page 1 of 1

## 9 Replies - 8593 Views - Last Post: 25 September 2012 - 05:41 AM

### #1 Serk102

Reputation: 2
• Posts: 9
• Joined: 19-June 11

# Best way to find all factors of a number?

Posted 19 September 2012 - 12:37 AM

So I'm not sure if this should go here, but I figured since it was fairly language agnostic and more math based, this should be the spot to post it. Sorry if it's not.

Anyways, basically what I'm trying to do is find all pairs of factors of a number, and I've got a program that does pretty much that.
```def getFactors(num):
factors = [[1, num]]
top = num**(1/2)
test = 2
while test <= top:
if num % test == 0:
factors.append([test, num // test])
test += 1
return factors

```

However it cannot take negative numbers as input, and I'm not sure this is the most efficient algorithm for finding all factors. I know I can increase efficiency if I don't check multiples of previously failed numbers(eg if n%2 != 0 then don't check any other even numbers), but I don't know how to implement something like this in a proficient way. Also I'm not sure if the method I'm using is the best because I did some googling, and read something about finding the prime factors, then finding the rest of the factors, but I'm not sure how that would work. Any help would be much appreciated, thanks!

Is This A Good Question/Topic? 0

## Replies To: Best way to find all factors of a number?

### #2 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12278
• Posts: 45,364
• Joined: 27-December 08

## Re: Best way to find all factors of a number?

Posted 19 September 2012 - 06:38 PM

You can use the Sieve of Eratosthenes to generate primes. The range you will want to use is 2-sqrt(n), since n will have at most sqrt(n) distinct pairs of (prime) factors. You can then use your iterative approach with the modulus operation to generate the factors.

http://en.wikipedia....of_Eratosthenes

### #3 Skydiver

• Code herder

Reputation: 6116
• Posts: 21,052
• Joined: 05-May 12

## Re: Best way to find all factors of a number?

Posted 20 September 2012 - 01:15 AM

Maybe I'm just missing a step, but I don't quite understand how having the prime factors will let me get all the pairs of factors.

Let's say the composite number that I want to get all the pairs of factors for is 16. By doing the sieving for 2-sqrt(16) -> 2-4:
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Now I try get factor pairs using the prime numbers that I have with the following pseudo code:
```num = 16;
prime_list = [ 2, 3 ]

for each prime in prime_list:
if num % prime == 0:
factors.append( [prime, num / prime] )

```

I end up with factors only containing [2, 8]. It doesn't contain [1, 16] or [4, 4].

If I follow the original approach above where [1, num] is automatically added, then [1, 16] will be included. Unfortunately, [4, 4] is still missing.

This post has been edited by Skydiver: 20 September 2012 - 01:20 AM

### #4 baavgai

• Dreaming Coder

Reputation: 7153
• Posts: 14,896
• Joined: 16-October 07

## Re: Best way to find all factors of a number?

Posted 20 September 2012 - 07:49 AM

Looks ok. Though, your top seems to be trimming too much.

Similarly, I do something like:
```def getFactors(num):
factors = [ 1 ]
factor = 2
while factor <num and factor not in factors:
if num % factor == 0:
factors.append(factor)
factor += 1
return [ (n, num/n) for n in factors ]

print('\n'.join( "{0} = {1}".format(i, getFactors(i)) for i in range(2,20) ) )

```

Prime factors are kind of fun, actually, and you don't need a sieve. You just whittle the poor number down:
```def getPrimeFactors(num):
factors = [ ]
factor = 2 # start here
while factor <= num: # we're going to reduce num
if num % factor == 0:
factors.append(factor)
num /= factor # retuce num
else:
factor += 1 # move on
return factors

print('\n'.join( "{0} = {1}".format(i, getPrimeFactors(i)) for i in range(2,20) ) )

```

Hope this helps.

### #5 jon.kiparsky

• Beginner

Reputation: 11022
• Posts: 18,805
• Joined: 19-March 11

## Re: Best way to find all factors of a number?

Posted 20 September 2012 - 08:26 AM

EDIT: where is my brain today?

This post has been edited by jon.kiparsky: 20 September 2012 - 08:34 AM

### #6 Skydiver

• Code herder

Reputation: 6116
• Posts: 21,052
• Joined: 05-May 12

## Re: Best way to find all factors of a number?

Posted 20 September 2012 - 09:09 AM

baavgai, on 20 September 2012 - 07:49 AM, said:

Looks ok. Though, your top seems to be trimming too much.

Similarly, I do something like:
```def getFactors(num):
factors = [ 1 ]
factor = 2
while factor <num and factor not in factors:
if num % factor == 0:
factors.append(factor)
factor += 1
return [ (n, num/n) for n in factors ]

print('\n'.join( "{0} = {1}".format(i, getFactors(i)) for i in range(2,20) ) )

```

Looks great. But won't this code now list both [2, 8] and [8, 2] as factor pairs for the number 16? Shouldn't the list of factor pairs only list one of [2, 8] or [8, 2] because multiplication is commutative?

### #7 baavgai

• Dreaming Coder

Reputation: 7153
• Posts: 14,896
• Joined: 16-October 07

## Re: Best way to find all factors of a number?

Posted 20 September 2012 - 10:34 AM

Nope and factor not in factors. It's why I went with one side of the pair on the loop.

Edit: Oops, you kind of asked two different questions... No, it won't give mirrored pairs. Yes, it should only list one.

This post has been edited by baavgai: 20 September 2012 - 10:36 AM

### #8 Skydiver

• Code herder

Reputation: 6116
• Posts: 21,052
• Joined: 05-May 12

## Re: Best way to find all factors of a number?

Posted 20 September 2012 - 11:18 AM

Maybe I'm reading the code incorrectly... Can you try to point out where I'm overlooking something?

In the case of num being 16. The first time through the loop, factor is 2. 16 % 2 == 0, so 2 is added to factors. The loop continues, and it adds 4. Eventually, factor will be 8. 8 is not in factors.

### #9 baavgai

• Dreaming Coder

Reputation: 7153
• Posts: 14,896
• Joined: 16-October 07

## Re: Best way to find all factors of a number?

Posted 20 September 2012 - 11:25 AM

Crap, you're right! Sorry about that.

Fixed:
```def getFactors(num):
factors = [ 1 ]
factor = 2
while factor <num:
if num % factor == 0:
if num/factor in factors:
break
factors.append(factor)
factor += 1
return [ (n, num/n) for n in factors ]

print('\n'.join( "{0} = {1}".format(i, getFactors(i)) for i in range(2,20) ) )

```

Results:
```2 = [(1, 2)]
3 = [(1, 3)]
4 = [(1, 4), (2, 2)]
5 = [(1, 5)]
6 = [(1, 6), (2, 3)]
7 = [(1, 7)]
8 = [(1, 8), (2, 4)]
9 = [(1, 9), (3, 3)]
10 = [(1, 10), (2, 5)]
11 = [(1, 11)]
12 = [(1, 12), (2, 6), (3, 4)]
13 = [(1, 13)]
14 = [(1, 14), (2, 7)]
15 = [(1, 15), (3, 5)]
16 = [(1, 16), (2, 8), (4, 4)]
17 = [(1, 17)]
18 = [(1, 18), (2, 9), (3, 6)]
19 = [(1, 19)]

```

### #10 Serk102

Reputation: 2
• Posts: 9
• Joined: 19-June 11

## Re: Best way to find all factors of a number?

Posted 25 September 2012 - 05:41 AM

Thanks to everyone who commented, I plan on using a combination of everything suggested to improve my algorithm, I'm especially interested in the sieve of eratosthenes.

Sent from my Nexus 7 using Tapatalk 2