[Serk102]

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!

[macosxnerd101]

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

[Skydiver]

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

[baavgai]

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.

[jon.kiparsky]

EDIT: where is my brain today?

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

[Skydiver]

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?

[baavgai]

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

[Skydiver]

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.

[baavgai]

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)]

[Serk102]

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