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).
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.
the number of primes less than is .
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)