# Prime factoring a large number.

• September 9th 2011, 10:41 AM
Gytax
Prime factoring a large number.
Is there a theorem or algorithm which would help me factor a 6-digit number into primes? I need to do it by hand (of course I can use a calculator, but not factoring programs or something like that).
• September 9th 2011, 11:09 AM
Prove It
Re: Prime factoring a large number.
Quote:

Originally Posted by Gytax
Is there a theorem or algorithm which would help me factor a 6-digit number into primes? I need to do it by hand (of course I can use a calculator, but not factoring programs or something like that).

Have you ever heard of a factor tree?

Prime Factorization
• September 9th 2011, 01:07 PM
Gytax
Re: Prime factoring a large number.
Quote:

Originally Posted by Prove It
Have you ever heard of a factor tree?

Prime Factorization

I can't just keep checking if that 6-digit number is divisible by every prime or other number up to 800. The first few primes don't work so I need something smarter to do. Any ideas?
• September 9th 2011, 01:26 PM
Plato
Re: Prime factoring a large number.
Quote:

Originally Posted by Gytax
I can't just keep checking if that 6-digit number is divisible by every prime or other number up to 800. The first few primes don't work so I need something smarter to do. Any ideas?

You said that you cannot use a calculator.
Then it has to be do 'by hand'
Each time you find a factor, that reduces the problem.
If the number is even, then 2 is a factor. Deduce it to half the number.
In each reduction, you need only test primes up to the square root of the reduced number.
• September 10th 2011, 01:32 AM
Gytax
Re: Prime factoring a large number.
I said that I can use a calculator, just not WolframAlpha via computer or that kind of solvers. That 6-digit is the product of two 3-digit numbers so I can't just check so much numbers.
• September 10th 2011, 05:10 AM
CaptainBlack
Re: Prime factoring a large number.
Quote:

Originally Posted by Gytax
I can't just keep checking if that 6-digit number is divisible by every prime or other number up to 800. The first few primes don't work so I need something smarter to do. Any ideas?

As a composite number $N$ has a prime divisor $\le \sqrt{N}$, for six digit numbers you only need check primes up to $\sqrt{N}$ and since

$\pi(N)\sim \frac{N}{\ln(N)}$

the number of primes less than $\sqrt(N)$ is $\sim \le \frac{1000}{\ln(1000)}\approx 145$.

So in general that is less than 145 trial divisions to find the first prime divisor, and every thing accelerates from there..

(There are in fact 168 primes less than the 1000)

CB