analytics

Thursday, April 4, 2013

Easy way to factor a number or tell whether it's prime

If T is the number you want to factor or know whether it is prime you can repeat this process recursively down until every factor is prime. First find s^2 the largest perfect square less than T. Then check whether this formula:

evaluates to a natural number for any natural number from 1 to s-2.  If it does the number is composite and is (s-a)*(s+f(a)). If it doesn't the number is prime.
For example the number 32 with everything plugged in:


You start with 1 and that evaluates to an integer: 3 so you know that 32=(5-1)*(5+3) or 4*8. We might have had to try 2 and 3 but didn't have to in this case. 

But if you try 31... 



This is never a natural number for n = {1...3} so 31 must be prime. 

*** Todo write out the proof I have it in my head but am trying to find the best way to say it**




No comments:

Post a Comment