Suppose that I am given a random, large (900+ digits) integer. I would like to edit a few of its digits so that the resulting integer is a prime. I am quite flexible on the definition of 'a few'. I would like the number to retain its length and as few edits as possible would be nice.
I would like to be able to find a prime as fast as possible. There are obvious things I should avoid:
- The last digit must be one of 1, 3, 7, 9
- The digit sum can't be a multiple of 3
- The alternating digit sum should not be a multiple of 11
Even with implementing these, this process will be very slow. Are there any other tricks that people have to offer?