Here's my code:
def factorize(n):
sieve = [True] * (n + 1)
for x in range(2, int(len(sieve) ** 0.5) + 1):
if sieve[x]:
for i in range(x + x, len(sieve), x):
sieve[i] = False
lowerPrimes = i for i in range(2, len(sieve)) if sieve[i]] and (n % i == 0)]
return lowerPrimes
factorize(n) returns all prime factors of the given value n. As you can see, it first makes an Eratosthenes sieve for n and then uses a list comprehension to return all values in the sieve that are factors of n. It works relatively fine for this purpose, however, I want it to return a list so that if you multiply every item in it, the result is n. Do you get my point?
For example, factorize(99020) returns [2, 5, 4951], but I'd like it to return [2, 2, 5, 4951], as 2*2*5*4951 = 99020.
I know my approach is not even close, but could you help me to make it so?
The Sieve of Eratosthenes helps you find prime numbers below a certain limit. It's not really going to help you with finding the factors of a particular number.
If you want to do that, the simplest approach that I can see is something like this:
def factors(n):
while n > 1:
for i in range(2, n + 1):
if n % i == 0:
n //= i
yield i
break
for factor in factors(360):
print factor
This basically finds the smallest factor of n (which is guaranteed to be prime), divides n by that number and repeats the process until n is equal to 1.
The output is:
2
2
2
3
3
5
They multiply out to the original number:
>>> from operator import mul
>>> reduce(mul, factors(360))
360