Prime Factors

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

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]

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

[TrustyTony]

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

[mciperf]

Much better!

[TrustyTony]

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