# Computer Program

1. Aug 31, 2008

### DanMarino

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)
thanks

2. Aug 31, 2008

### symbolipoint

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.

3. Sep 1, 2008

### HallsofIvy

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.

4. Sep 1, 2008

### CRGreathouse

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.

5. Sep 2, 2008

### HallsofIvy

The problem was to factor a number. I assumed a sufficiently large list of primes was available.

6. Sep 2, 2008

### CRGreathouse

I was just explaining to give 'your' method generality without requiring a list of primes exceeding sqrt(n) in size.