9514 1404 393
680624 = 2^4 · 7 · 59 · 103165649 = 11^2 · 37^2
Step-by-step explanation:
Using the division method, you find prime divisors that give integer quotients until the final quotient is a prime. For small divisors, it is beneficial to make use of divisibility rules. For larger ones, you just have to try the list of primes to see what you get.
680624
The last two digits are divisible by 4, so the number can be divided by 2 twice (at least). We can keep dividing by 2 as long as the 1s digit is even.
680624/2 = 340312
340312/2 = 170156
170156/2 = 85,078
85078/2 = 42539
The next prime is 3. The divisibility rule for 3 is the sum of digits must be divisible by 3. 4+2+5+3+9 = 23, not divisible by 3.
The next prime is 5. For divisibility by 5, the number must end in 0 or 5. This is not divisible by 5.
The next prime is 7. For divisibility by 7, there are several possible rules you can use. One I find relatively easy to remember is to subtract double the 1s digit from the rest of the number and see if that is divisible by 7. Here, that gives ...
4253 -2(9) = 4235; 423 -2(5) = 413; 41 -2(3) = 35 . . . divisible by 7
Continuing, we have ...
42539/7 = 6077
There are additional divisibility rules for 11 and 13 that can be applied. For divisibility by 11, we can add pairs of digits: 77 +60 = 137, not divisible by 11.
For divisibility by 13, we can add 4 times the last digit to the rest:
4253 +4(9) = 4289; 428 +4(9) = 464; 46 +4(4) = 62 . . . not divisible by 13
__
After this point, it is a matter of trying the primes one by one to see what the number may be divisible by. This "trial and error" will show you ...
6077/59 = 103 . . . 103 is prime, so we're done
The final factorization is ...
680624 = 2^4 · 7 · 59 · 103
__
165649
As luck would have it, this is a perfect square, so we can immediately reduce the problem to something a little easier.
√165649 = 407
We can see "immediately" that this is not divisible by 2, 3, 5, or 7. However, 04+07 = 11, so this is divisible by 11.
407/11 = 37 . . . 37 is prime, so we're done
The final factorization is ...
165649 = 11^2 · 37^2
As you can probably tell, it is convenient to have a list of prime numbers available. Here is a list of the first few primes.
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59,
61, 67, 71, 73, 79, 83, 89, 97, 101, 103
Additional comment
If you start with the smallest primes, (2, 3, 5}, once you find a prime divisor, you only need to try primes greater than or equal to that one on the quotient. In any event, you only need to try primes up to the square root of the value you're trying to factor. If none of those work, then the number itself is a prime.
In the first problem, once we got to 6077, we would only need to try primes up to √6077 ≈ 77. That is, if 6077 turned out to be not divisible by any prime equal to 73 or less, then 6077 would be the last prime factor. (As we found, 6077 is composite, not prime, so using that number is just to illustrate the point regarding the largest value needed to be tested.)
