Q: you replied to a question: "i can find the prime factorization of 6 digit numbers in my head" do you have a trick to do this? how would I find the prime factorization of 239429 in my head?
A: since it's already odd and doesn't have 5,  check for 3. the check for 3 is if the digits add up to another multiple of 3. you can also do this by knocking off all multiples of 3 you see in the digits, even if it's multiple digits next to each other. so delete the 9s, delete the 3, and delete the "42". and you're left with 2 which is not a multiple of 3 so we've ruled out 3. Now you just start moving through the prime numbers, checking each one. there are many different tricks here, but it's generally the same strategies for every other prime from now on. let's say we're checking for 7 (the next prime to check for). see the 23, on the left? that's close to 21, so let's change that to 2.  == 29429. what this means is, we just subtracted 210000 from the original number. so what this means is, if the original number is a multiple of 7, then 2949 has to be a multiple of 7 also because we just subtracted 210000 (which is clearly a multiple of 7).  basically we manipulate the original number by multiples of 7, until it is simple enough to see whether the resulting number is a multiple of 7. and if it is, congratulations the original number was a multiple of 7 also. in the manipulations, you are allowed to add or subtract any multiple of 7, and you can also multiply or divide by anything you want. so from 29429, i can see "42" in there, so you can just replace that with zero 29009 (we just subtracted 420, which of course is a multiple of 7).  now let's add 21 == 29030, knock off the zero at the end (you can divide this by 10 and it won't effect whether or not it's a mutiple of 7, so you can knock off zeros on the end all you want.) so 2903. now let's add 7 == 2910, knock off the zero = 291.  (you can see the strategy, we're adding/subtracting small multiples of 7 based on whatever can even off the end to have a zero at the end, because then we can kill the zero and the number shrinks and still has its same status with regard to being a multiple of 7 or not.)  so from 291, take off 21 is 270, knock off the zero is 27. which is clearly NOT a multiple of 7. basically i'm adding and subtracting multiples of seven to get the number simpler and simpler until eventually we can tell if the resulting number is a multiple of 7.   and if you couldn't see whether 27 was a multiple of 7 then you could just knock off the 7 and it's 20, knock off the zero is 2. which is not a multple of 7. So congratulations, the original number (239429) is not a multiple of 7. Next we check for 11s. i would start with the left again, because 23 is so close to 22. replace it with 1 == 19429. then add 11 to the right,(and kill the zero) 1944. you can knock off 44, and pow, 19, not 11. so 11 is ruled out. Then start again for 13.  from the left, change the 23 to 10 (effectively subtracting 130000), == 109429. '109' is 5 above 104 which i happen to know has 13 in it, so replace 109 with 5. == 5429.  54 is 2 above 52, which i happen to know has 13 in it, so 229. what's the nearest multiple of 13 above 229? 260. is that a multiple of 13 away? can't be because the only one in that century with 1 at the end of it is 91 and it's not 91 away (it's 31 away, again non-13.) so 13 is out. now check for 17. repeat this process through the primes, 17, 19, 23, 29, 31, etc etc.  and you may be wondering "how far do i have to go before knowing if the original number is prime." well the answer is, if you are checking them all in order and you do it correctly, the process is guaranteed complete once you reach the square root of the original number. the way to loosely figure that out is, look at 250000. square root of that should be 5 with zeros ...500 times 500 should be 250000. so in this case if you check all the primes up to 500 and you don't find a match then you know you can stop. but if you find a match at let's say 31, then you divide the thing by 31 and then you have a much smaller number to work with, and find the primes there. then when you're done just include 31 as well. by the way i didn't check 31 in this example so 31 probably is not in there