How to Write a Prime Factorization Program in Computer

[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)
please help
thanks

 

[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.

 

[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, p_i, divides n. If yes, record that fact and repeat with the quotient, n/p_i 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 p₁= 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 p₂= 3. Does 3 divide 3? Yes, so record a 3. 3/3= 1 so we are done.

 

[CRGreathouse]

Yes, so record a 3. 3/3= 1 so we are done.

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.

 

[HallsofIvy]

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

 

[CRGreathouse]

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

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