# Algorithm for prime factorization

1. Jan 26, 2009

1. The problem statement, all variables and given/known data

One algorithm for finding the prime factorization of a number n is the following: Starting with d = 2, and continuing until n$$\geq$$d, try to divide n by d. If n/d, then record d as a (prime) factor and replace n by n/d; otherwise replace d by d + 1.

a) When d is recorded, how do we know that d is prime?
b) Suppose n = ab. Show that a$$^{2}$$$$\leq$$n or b$$^{2}$$$$\leq$$n
c)Use this fact to improve the algorithm.

2. Relevant equations

see above

3. The attempt at a solution

for part a, since we are dividing by a prime number that is how we know that d is prime. I dont know how to do part b but, i think it might have something to do with a/p or b/p, where p is the prime number.

Last edited: Jan 27, 2009
2. Jan 26, 2009

### Dick

I think you mean replace n by n/d. But if you are starting with d=2 and dividing n by d, then incrementing d and trying again, for the FIRST value of d that divides n, d MUST be prime. Can you say why?

3. Jan 27, 2009

i corrected the error. I'm still unsure about this but the fundamental theorem of arithmetic states that every natural number greater than 1 can be written as a unique product of prime numbers, since d is the first number we are dividing it by, therefore it must be prime.

4. Jan 27, 2009

### Dick

That's not super clear. But if d isn't prime then it's divisible by another number. Say e. And e<d. What does that mean in terms of the algorithm?

5. Jan 27, 2009

### symbolipoint

One way to handle the factorization is to divide only by prime numbers. I made a factorization program a few years ago. I used the Sieve of Eratosthenes process to find a list of primes, and then I performed a succession of divisions up to a certain value (square root of something,... forgot the exact reason for this).

6. Jan 27, 2009

the only number less than d would be 1 then but the fundamental theorem of arithmetic says that it should be greater than 1, so the next prime number is 2.

7. Jan 27, 2009

### Dick

You still don't get it. If you start from 2 and divide n by successive integers, the first d that divides n MUST be prime, otherwise you would have divided n with another integer before you hit d. Right? Right? Right? Don't just quote abstractions, think about it.

8. Jan 27, 2009

so if i take n=32 for example then 32/4=8, and 8/4=2, 2/2=1. got it. btw i'm also having some trouble doing part c).

9. Jan 27, 2009

### Dick

It's what symbolpoint said. If you don't find a divisor before you hit sqrt(n), you may as well quit. You aren't going to find one. Why?

10. Jan 27, 2009

is it because the n/d would no longer be divisible by d, if a<=sqrt(n) or b<=sqrt(n) then can it be that ab<n??? I donr really know how to answer this.

11. Jan 28, 2009

### Dick

If n=a*b, that's a factorization of n. If both factors were greater than sqrt(n) then a*b>n. That can't be since a*b=n. So at least one of factors a or b must be less than sqrt(n).

12. Jan 28, 2009