#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Oct 2013
    Posts
    8
    Rep Power
    0

    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.
  2. #2
  3. Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    May 2012
    Location
    39N 104.28W
    Posts
    158
    Rep Power
    3
    [(i,a/i) for i in xrange(1,a) if a%i==0]

    so, if a=8: [(1, 8), (2, 4), (4, 2)]
  4. #3
  5. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,841
    Rep Power
    480
    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 03:56 PM. Reason: bug found and eliminated.
    [code]Code tags[/code] are essential for python code and Makefiles!
  6. #4
  7. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Oct 2013
    Posts
    8
    Rep Power
    0
    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!
  8. #5
  9. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,841
    Rep Power
    480
    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 03:58 PM.
    [code]Code tags[/code] are essential for python code and Makefiles!
  10. #6
  11. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Oct 2013
    Posts
    8
    Rep Power
    0
    Thanks for you help!!

    That very helpful, I now understand TY.
  12. #7
  13. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,841
    Rep Power
    480
    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!

IMN logo majestic logo threadwatch logo seochat tools logo