+23 Find the largest prime factor of 1,005,010,010,005,001 without using brute force.
+744 The number we're looking at is interesting because it can be expressed as a difference of squares:
1,005,010,010,005,001 = (1005^2) - (1^2)
We can use a property of difference of squares to our advantage: a^2 - b^2 = (a + b)(a - b). In this case:
(1005^2) - (1^2) = (1005 + 1)(1005 - 1) = 1006 * 1004
Now, 1006 is even (because the last digit is 6), so it's not prime. We can focus on 1004.
Looking closely at 1004, we see that the last two digits are 04, which is a multiple of 4. Therefore, 1004 is also even and not prime.
However, 1004 can be further factored: 1004 = 2 * 2 * 251. Here, 251 is odd, and a quick primality check reveals it is a prime number.
Therefore, the largest prime factor of 1,005,010,010,005,001 is 251.
