Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Computer Program

  1. Aug 31, 2008 #1
    i need to know how to write a program that will break a number down into its prime factors.
    for example you would input the number 24 and the computer will break that up into its prime factors (2*2*2*3)
    please help
    thanks
     
  2. jcsd
  3. Aug 31, 2008 #2

    symbolipoint

    User Avatar
    Homework Helper
    Education Advisor
    Gold Member

    You can literally use Sieve of Eratosthenes if you want. Not too difficult to develop as a computer program. I've done it just a few years ago, but right now the code is not in a convenient place to refer. Maybe you can develop your own version or find through an internet search. I used arrays in mine and filled consecutive primes into the arrays. Maybe someone else knows a faster method. Maybe someone else knows something better than Sieve of Eratosthenes.
     
  4. Sep 1, 2008 #3

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    The sieve of Eratosthenes is a method of producing prime numbers but that is not the problem here. Here's what I would do:

    1. First get a list of prime numbers at least up to the square root of n, perhaps using the sieve of Eratosthenes.

    2. Step through your list of primes, testing whether the ith prime number, pi, divides n. If yes, record that fact and repeat with the quotient, n/pi until that quotient is 1. If you get up to the square root of n without finding any divisors, n is prime iteself.

    With your example of 24, We would first check p1= 2. Does 2 divide 24? Yes, so record a 2. 24/2= 12. Does 2 divide 12? Yes, so record a 2. 12/2= 6. Does 2 divide 6? Yes, so record a 2. 6/2= 3. Does 2 divide 3? No so go on to p2= 3. Does 3 divide 3? Yes, so record a 3. 3/3= 1 so we are done.
     
  5. Sep 1, 2008 #4

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    This example has no large prime factors. If after finishing the loop a number more than 1 remains, it is prime and can simply be added to the list.
     
  6. Sep 2, 2008 #5

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    The problem was to factor a number. I assumed a sufficiently large list of primes was available.
     
  7. Sep 2, 2008 #6

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    I was just explaining to give 'your' method generality without requiring a list of primes exceeding sqrt(n) in size.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?