## diniboi

Whats up guys?

This program has given me nightmares lol.
When input is a positive integer, the program should reduce it to prime factors. The integer is less than 900. The program should Output the prime factors as a series that when multiplied together, will return the original integer.

If Input:
660
Output:
660 = 2.2.3.5.11

The code that i have tried to create is not finished and its hard coded so does anyone have ideas on how to write a program that would output the above result.

## griswolf 304

So show the code.

Here's a hint:

``````primes = set((2,3,5,7))
factors = []
for p in primes:
if 0 == num%p:
num /= p
factors.append(p)``````

Now re-do this code so as to check even more possible factors, and handle multiples of the same prime. You can do it two ways:

1. Dynamically add primes to the set of primes while checking
2. Create a list of "all possible prime candidate factors" first, then check them all

Option 1 is more efficient, but option 2 is easier to think about.

Hint: you don't need to consider all primes smaller than your number. What is the upper limit?

Hint: There are a lot of examples of code that finds prime numbers, including several here at Daniweb. Go look for them.

## diniboi

Here's my code with additions :

``````def get_factors(num):
L = []
NewL = []
FinalL = []
for x in range(2, int(num**0.5)+1):
if num % i == 0:
L = L + [i]
for x in L:
c = num/x
if c not in NewL:
NewL = NewL + [c]
FinalL = L + NewL
FinalL.sort()
return FinalL
def prime(num):
L2 = []
for i in range(2, num+1):
if get_factors(i) == []:
L2 = L2 + [i]
return L2

num = int(raw_input())
p = prime(num)
print num," = ",p

primes = set((p))
factors = []
for z in primes:
if (0 == num%z):
num /= z
factors.append(z)
factors.sort()``````

But as you can see it still not working correct, this is what it suppose to look like:

Input:
660

Output:
660 = 2.2.3.5.11

The output of the prime factors when multiplied should equal my original input.

## griswolf 304

when I ran this code, the first thing I saw was

``````File "pf.py", line 6, in get_factors
if num % i == 0:
NameError: global name 'i' is not defined``````

Which is what you would have seen too, no? So did you look at that error and fix line 6 (or above)?

## mciperf

This works: gen_primes could be improved for speed, but not an issue for this range.

``````import math

primes = [2, 3]

def gen_primes(n):
"""return a list of factors up to sqrt(n)"""
primes = [2,3]

upper = int(round(math.ceil(math.sqrt(n)))) + 1

for k in xrange(3, upper):
divisors = [p for p in primes if k % p == 0]
if not divisors: primes.append(k)

return primes

def factors_f(n):
assert 2 <= n <= 900
factors = []
for p in primes:
while n % p == 0:
factors.append(p)
n /= p

return factors

primes = gen_primes(900)
print primes
factors = factors_f(660)
print factors
factors = [str(f) for f in factors]
print " * ".join(factors), "=", 660``````

## pyTony 888

Again without code-tags!

``````import math

primes = [2, 3]

def gen_primes(n):
"""return a list of factors up to sqrt(n)"""
primes = [2,3]

upper = int(round(math.ceil(math.sqrt(n)))) + 1

for k in xrange(3, upper):
divisors = [p for p in primes if k % p == 0]
if not divisors: primes.append(k)

return primes

def factors_f(n):
assert 2 <= n <= 900
factors = []
for p in primes:
while n % p == 0:
factors.append(p)
n /= p

return factors

primes = gen_primes(900)
print primes
factors = factors_f(660)
print factors
factors = [str(f) for f in factors]
print " * ".join(factors), "=", 660
``````

Much better!

## pyTony 888

For this range I would use most primitive possible factor function for simplicity:

``````from operator import mul
try:
from functools import reduce   # for Python3
except ImportError:
pass

def factors(x):
divisor = 2
if x < 4:
if x < 0:
yield -1
x = -x
else:
yield x
return
while True:
while not x % divisor:
x //= divisor
yield divisor
divisor = 3 if divisor == 2 else divisor + 2
# x this moment, not original x!
if divisor * divisor > x:
yield x
return

for n in range(-30, 901):
print('%4i' % n, '.'.join(str(f) for f in factors(n)))
assert reduce(mul, factors(n)) == n``````