I was given a random 4-digit number to factor over the prime numbers. My number was 8,023. I tried applying all the divisibility rules up to 36 before giving up on them. I tried using algebra as follows
$$8023=(10a+9)(10b+7),\space a>3,\space b>2$$
or $$8023=(10a+3)(10b+1),\space a>3,\space b>3$$
but this was very tedious and inefficient for the time limit. It was not feasible to apply brute force manually to both equations. I could not find a way to narrow down a or b within the time limit.
I ended it thinking it was prime, but
$$8023=71*113$$
Is there a method to efficiently factor smaller numbers with obscure factors such as 8023?
Factor numbers like 8,023 manually
elementary-number-theoryfactoringprime factorizationprime numbers
Best Answer
It is tedious. If n is random, you’d check if n is 0 or 1 (neither prime nor composite), whether n is 2, 3, 5 (prime), divisible by 2, 3, 5 (check the last digit it the sum of digits) and then n < 49 is prime.
Since 7x11x13 = 1001, you check if n modulo 1001 is divisible by 7, 11, or 13, and then everything less than 289 is prime. At this point less than one in five composite numbers remain.
If n < 10,000 then trial division is likely fastest. Above that you can look at the pollard-rho method; if n has a prime factor p then pollard-rho will very likely find it in say 3 sqrt(p) steps and often in sqrt(n) steps, that would be 30 steps for n = 10,000 or 100 steps for n = 1,000,000 or 500 steps for n = 1 billion. The problem is it doesn’t work for primes, so if it takes too long to find a factor then you’d use likely a non-deterministic primality test.