Results 1 to 1 of 1

Thread: Prime Factor Decomposition

  1. #1
    Ah, Mrs. Peel! mike_w's Avatar
    Join Date
    Oct 2003
    Location
    Hertfordshire, England
    Posts
    3,326
    Thanks
    3
    Thanked
    9 times in 7 posts

    Prime Factor Decomposition

    The title gives most of it away - what's the quickest way to reduce any number down to its prime factors using a computer?

    In case you don't know what prime factor decomposition is:

    You can break down any non-prime number into two numbers. If either of those aren't prime, you can break them down into two more numbers each, and so on, until all you're left with is prime factors e.g.

    1000 = 10 * 100
    10 = 2 * 5, 100 = 2 * 50
    So: 1000 = 2 * 5 * 2 * 50
    50 = 5 * 10
    So: 1000 = 2 * 5 * 2 * 5 * 10
    10 = 2 * 5
    So: 1000 = 2 * 5 * 2 * 5 * 2 * 5
    1000 = 2^3 * 5,^3

    I've been using Python, and the best I've come up with is this:

    Code:
    def PrimeFactors(original):
    	results = [int(original)]
    	factor = 2
    	while factor < original:
    		if original % factor == 0:
    			del results[0]
    			results.extend([factor])
    			results.extend(PrimeFactors(original / factor))
    			return results
    		factor = factor + 1
    	return results
    The basic principle is:
    1) Find the first factor by starting with 2 and working upwards
    2) Stick the first factor into the list, since it must be prime
    3) Find the factors of the second factor using the same method
    4) Keep on going until all you're left with are prime factors

    However, as you might expect, it gets rather slow once you get onto higher digit numbers. Can anybody think, or know, of a faster method?

    Thanks

    Mike.

    Edit: Oh, I know that Python is slow at this. Is there an easy way of sticking C code into a Python program?
    Last edited by mike_w; 14-04-2006 at 08:31 PM.
    "Well, there was your Uncle Tiberius who died wrapped in cabbage leaves but we assumed that was a freak accident."

Thread Information

Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)

Similar Threads

  1. been running 2 instances of prime for 11 odd hours hours is tyhat enough ?
    By weebroonieuk in forum PC Hardware and Components
    Replies: 17
    Last Post: 15-02-2006, 07:31 AM
  2. Weird beeping sounds when running PRIME 95.
    By Noni in forum PC Hardware and Components
    Replies: 6
    Last Post: 22-01-2006, 11:47 AM
  3. Alright... Overclocking an A64.. Where do I start...?!?!? Dizzy....
    By sawyen in forum PC Hardware and Components
    Replies: 31
    Last Post: 16-06-2005, 10:17 AM
  4. Glitch in Prime 95
    By Spritzup in forum PC Hardware and Components
    Replies: 6
    Last Post: 16-02-2004, 02:43 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •