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

#1 Serk102  Icon User is offline

  • New D.I.C Head

Reputation: 2
  • View blog
  • 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  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10595
  • View blog
  • Posts: 39,236
  • 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
Was This Post Helpful? 0
  • +
  • -

#3 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3589
  • View blog
  • Posts: 11,157
  • 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

Was This Post Helpful? 0
  • +
  • -

#4 baavgai  Icon User is online

  • Dreaming Coder
  • member icon

Reputation: 5846
  • View blog
  • Posts: 12,703
  • 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.
Was This Post Helpful? 3
  • +
  • -

#5 jon.kiparsky  Icon User is offline

  • Pancakes!
  • member icon


Reputation: 7802
  • View blog
  • Posts: 13,197
  • 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

Was This Post Helpful? 0
  • +
  • -

#6 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3589
  • View blog
  • Posts: 11,157
  • Joined: 05-May 12

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

Posted 20 September 2012 - 09:09 AM

View Postbaavgai, 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?
Was This Post Helpful? 0
  • +
  • -

#7 baavgai  Icon User is online

  • Dreaming Coder
  • member icon

Reputation: 5846
  • View blog
  • Posts: 12,703
  • 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

Was This Post Helpful? 0
  • +
  • -

#8 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3589
  • View blog
  • Posts: 11,157
  • 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.
Was This Post Helpful? 1
  • +
  • -

#9 baavgai  Icon User is online

  • Dreaming Coder
  • member icon

Reputation: 5846
  • View blog
  • Posts: 12,703
  • 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)]


Was This Post Helpful? 1
  • +
  • -

#10 Serk102  Icon User is offline

  • New D.I.C Head

Reputation: 2
  • View blog
  • 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
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1