# Quick way to find big prime numbers

I recently found myself in need of a “big” prime number, with about a hundred digits (which is still quite reasonable to compute). While there exists sophisticated solutions to find such a number, I thought prime numbers are dense enough so that the following algorithm is sufficient:

q = random integer with a hundred digits while q is not a prime number: increment q

Indeed, the probability \(p(q)\) for an integer \(q\) to be prime is \(\approx 1 / \log(q)\), so if \(q\) has a hundred digits we have \(p(q) \approx 10^{-3}\). Starting from a random integer of a hundred digits, we’re not likely to consider more than a thousand candidates among its successors before we get a prime number.

In Sage, it goes like this:

q = randint(10^99, 10^100) while not is_prime(q): q += 1

And the result I got is:

sage: q 91161119841079943034864082382910657827892098896935 58465300172406379775170630402227270198354615711887

Execution time was about 0.1 seconds. Well, that's it!