# Number of numbers need to check before finding a prime

I am interested in (roughly estimating) how many random integers do I have to check before I find a prime of size say $100$ digits.

I was thinking like so:

Let the number of primes up to $X$ be denoted by $\pi(X)$. The famous Prime Number Theorem says that $$\lim_{X\to\infty}\frac{\pi(X)}{X/\ln(X)}=1$$ so a randomly chosen number $N$ has probability $$P(N \ being \ prime)=\frac{1}{\ln(N)}$$ of being prime.

Now I need numbers of size $10^{100}$ which means I have $$\frac{1}{\ln(10^{100})}=\frac{1}{100}\cdot \frac{1}{\ln(10)}\approx 0,02305$$

so the chance of picking a prime is roughly $2,3\%$ therefore I need (in theory) to check at least $50$ numbers before I hit a prime.

Is my reasoning correct?

Thank you!

Edit:

I made a silly calculator mistake the correct value is: $$\frac{1}{230}\approx 0,00434$$ so I need to check a bit over $200$ numbers say $250$.

• You are not going to bother checking even numbers, are you? May 1 '18 at 6:05
• The numerical value is not correct. It is about $\frac{1}{230}$. Of course, with trial division (lets say upto $100$) , you can speed up the search and you increase the chance to find a prime by a factor of $8.3$ if you try large numbers.. Basically , your approach is correct however. May 1 '18 at 6:05
• No definitely not, in a realistic case (further non ending with 5 etc) :) But the question said "random integers" so I assume they mean actually a randomly picked integer May 1 '18 at 6:06
• @Peter thank you. I corrected the question. I made a silly calculator mistake May 1 '18 at 6:12
• I have recently read that this approach (probability $\frac{1}{\ln(N)}$) has been refuted, but this should not be critical. I do not think that the error is big. May 1 '18 at 6:19

There was a Polymath Project (see link here) to come up with an efficient deterministic algorithm to find a prime larger than a given number $N$ (equivalent to a prime of size at least $\lceil \log_2 N \rceil$ bits in your notation). Terence Tao led this effort and a paper (see abstract here) was published at the end of the project.
I quote from the introduction of the paper, which confirms your guess of the randomized complexity, as being essentially $O(\log^{O(1)}N)$:
Note that if one allows probabilistic algorithms [..] one can accomplish this in time polynomial in the length of $N$ (i.e. in time at most $\log^{O(1)} N$); indeed, one can select integers in [N, 2N] at random and test each one for primality. [..] Using algorithms such as the AKS algorithm, each such integer can be tested in time at most $\log^{O(1)} N$, and by the prime number theorem one has about a $1/ \log N$ chance of success with each attempt, so the algorithm will succeed with (say) 99% certainty after at most $\log^{O(1)} N$ units of time
Note: The notation $\log^c N$ is used for $(\log N)^c$ here. AKS (Agarwal-Kayal-Saxena) algorithm which is used in the paper is a deterministic primality test with original complexity $O(\log^6 N)$ for a number of bitsize $N$, and it's since been improved to $O(\log^3 N)$ later. If this algorithm states that a number is prime, the number is indeed a prime, not subject to errors.