Just some fun finding factors

find_factors.py

# this method will return a pair of prime numbers which, when multiplied, equal the argument
def find_factors(num):
	if num == 0: return (0,0)
	# if not prime ...
	for i in [2]+range(3, num/2+2, 2):
		if num % i == 0:
			return (i, num/i)
	return (1, num)

def sieve_primes(SIEVE_SIZE):
	#sieve = [True for i in range(SIEVE_SIZE)]
	sieve = [True] * SIEVE_SIZE
	sieve[0] = sieve[1] = False
	for n in range(2,SIEVE_SIZE):
		if not sieve[n]: continue
		for m in range(n,SIEVE_SIZE,n):
			sieve[m] = False
		sieve[n] = True
	return [i for i in range(len(sieve)) if sieve[i]]

def find_factors_2(num):
	primes = sieve_primes(num) # +1 (?)
	low = 0
	high = len(primes) - 1
	#print primes, num
	while primes[low] * primes[high] != num:
		#print primes[low], primes[high]	
		if primes[low] * primes[high] < num:
			low = low + 1
		else:
			high = high - 1
		#print (primes[low], primes[high])

	return (primes[low], primes[high])

from random import randint
def test(p): # p is a list of primes
	a = randint(0, len(p)-1)
	b = randint(0, len(p)-1)
	if a > b:
		a,b = b,a
	print "testing ", (p[a],p[b]), p[a]*p[b]
	r = find_factors_2(p[a]*p[b])
	print "got ", r
	return r == (p[a],p[b])