Make a prime number from specified number, by concatenating some more digits on its right?

Question

I am given a number, I don't know whether it's prime or not. The algo says,
For eg -
Step 1 - Convert char to ints. (Hello - 72101108108111) Ascii values
Step 2 - Make a large number.

1. Convert char to ints. (Hello - 72101108108111) Ascii values
   
2. Make a larger number (72101108108111).
3. Make this number a prime by adding more digits. .
   .
   .
   .
   I want to know, how the algo expects to add some more digits to the right , So I would get a prime?

Answer 1

What I would do is the following :

1. Add a digit at the end of the number to make it of the form $6k+1$ (this is always doable).
2. Test the number for primality using the Miller-Rabin Test.
3. If the number is prime, stop and return the number.
4. The number isn't prime. Add a $3$ at the end. The number still has the form $6k+1$. Go to step 2.

Making the number of the form $6k+1$ prevents the number you create to be divisible by $2$ and $3$ and increases the probability that you find a prime number.

EDIT : Unfortunately this doesn't work for all numbers. I would advise you to test all odd numbers (not multiples of 5) that can be produced by concatenating numbers at the right, in the increasing order, and testing each one of them with a primailty test, as in Charles' answer.

Answer 2

Use brute force. Take the large number $N$ and test if any of $10N+1,10N+3,10N+7,$ or $10N+9$ are prime. If so you're done. If not, test $100N+1,100N+3,\ldots,100N+97,100N+99.$ If none of those are prime check $1000N+1$ and so on. This is guaranteed (by the Prime Number Theorem) to eventually find a prime.