# 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!

## Discussion

You can use Markdown with $\LaTeX$ formulas in your comment.