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

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


There are no comments yet. Feel free to leave a reply using the form below.

Post a comment

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

You agree to the publication of your comment on this page under the CC BY 4.0 license.

Your email address will not be published.

© Stéphane Caron — All content on this website is under the CC BY 4.0 license.