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
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.
As a composite number has a prime divisor , for six digit numbers you only need check primes up to and since
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)
CB