January 5th, 2014, 08:51 AM

Can someone help me please!
Hi,
I am struggling to try a write a programme to do the following:
return a list of prime factors.
any help would be awesome thanks.
January 5th, 2014, 11:51 AM

[(i,a/i) for i in xrange(1,a) if a%i==0]
so, if a=8: [(1, 8), (2, 4), (4, 2)]
January 5th, 2014, 10:13 PM

Prime factoring is a fundamental operation of executable Iverson notation
Code:
q: 8 NB. prime factors of 8
2 2 2
q:60 NB. prime factors of 60
2 2 3 5
2 p: 60 NB. prime factors with exponent
2 3 5
2 1 1
(; (2 p: ])) */ 2 2 7 11 11 11 31 31
┌────────┬─────────┐
│35814548│2 7 11 31│
│ │2 1 3 2│
└────────┴─────────┘
2 p: 8
2
3
What can we do in python? With respect to efficiency, how can you improve this function assuming it will be reused to factor many numbers?
Code:
def prime_factor(factor_me):
'''
>>> prime_factor(35814548)
[2, 2, 7, 11, 11, 11, 31, 31]
>>> #Lambert Electronics,
>>> # LLC, NY. USA
>>> prime_factor(11)
[11]
'''
n = factor_me
prime_factors = []
for potential_factor in range(2, 1+int(0.5 + factor_me**0.5)):
if n == 1:
break
while n % potential_factor == 0:
prime_factors.append(potential_factor)
n /= potential_factor
if 1 < n:
prime_factors.append(n)
return prime_factors
Last edited by b49P23TIvg; January 6th, 2014 at 04:56 PM.
Reason: bug found and eliminated.
[code]
Code tags[/code] are essential for python code and Makefiles!
January 6th, 2014, 04:18 PM

Thanks for you reply b49P23TIvg.
I am fairly new to programming, I am having difficulty understanding how the code works.
I cant seem to get it to work in Python 2.7.5, am I doing something wrong maybe?
Do I need to edit anything within the code to get it to work ?
Thanks again!
January 6th, 2014, 04:55 PM

Code:
def prime_factor(factor_me): # prime_factor is a function taking one argument, the number to factor
'''
####From your shell command python m doctest v thisfile.py to run the test
>>> prime_factor(35814548)
[2, 2, 7, 11, 11, 11, 31, 31]
>>> #Lambert Electronics,
>>> # LLC, NY. USA
>>> prime_factor(11)
[11]
>>> prime_factor(121)
[11, 11]
'''
n = factor_me # make a copy of the number to factor
prime_factors = [] # prepare a list to store the prime factors
for potential_factor in range(2, 1 + int(0.5 + factor_me**0.5)): # the candidate factors are 2, 3, ... sqrt(factor_me)
if n == 1: # Finished when n is reduced to 1.
break
while n % potential_factor == 0: # while the potential factor divides without remainder into n. The while loop ensures we find all of the same factor.
prime_factors.append(potential_factor) # append the factor to the list of prime factors of factor_me
n /= potential_factor # reduce n
if 1 < n: # n is prime
prime_factors.append(n)
return prime_factors
I originally tested the program in python 2.7. Perhaps the problem is that you need to learn what is a function and how to use one? Study the python tutorial.
Last edited by b49P23TIvg; January 6th, 2014 at 04:58 PM.
[code]
Code tags[/code] are essential for python code and Makefiles!
January 6th, 2014, 05:04 PM

Thanks for you help!!
That very helpful, I now understand TY.
January 7th, 2014, 10:57 AM

When finding the prime factors of 720 my program uses 12 as one of the candidates. What happens?
If useful, how can you make sure 12 is tested?
If not useful, how can you prevent testing the trial divisor 12?
Generalize, and write an efficient factoring program.
[code]
Code tags[/code] are essential for python code and Makefiles!