Probability of correctly declaring number as prime It is known that a way to check whether a number $n$ is prime, is to check for divisors of $n$ from $2$ to $\lfloor\sqrt{n}\rfloor$. If we find any divisor, then $n$ is not prime. If we don't, then we don't need to check for divisors bigger than $\sqrt{n}$ (and $n$ is prime).
An "approximation" of this method would be to check for divisors the same way but from $2$ to $log_2n$. If we find any divisor we declare that $n$ is not prime. If we don't find any divisor we declare that $n$ is prime. Of course this method will not always give the correct results. My question is:
If the second algorithm declares a number to be prime, what is the probability that this number is actually prime?
 A: For very large numbers we can estimate the probability as follows :
Let $N$ be the given number , then $M:=\frac{\ln(N)}{\ln(2)}$ is the limit of trial division.
Denote $$P:=\prod{\frac{p}{p-1}}$$ where $p$ runs over the primes upto $M$, if $M$ itself is very large, we can approximate this as $$P\approx \frac{e^{-\gamma}}{\ln(M)}$$ where $\gamma$ is the Euler-Mascheroni-constant.
Then, the probability that we have a prime, if no factor is found, is roughly $$\frac{P}{\ln(N)}$$
For numbers $N\approx 10^{99}$ , we get about $4.6$%
A: Suppose $n$ is a random positive integer from $1$ to $N$.  By the Prime Number Theorem, the probability that it is prime is on the order of $1/\log N$.  On the other hand, for each
prime $p < \log N$ the probability that it is not divisible by $p$ is $1 - 1/p$, so the probability that it has no prime factors $< \log N$ is on the order of
$$ \prod_{p \le \log N} (1 - 1/p) \approx \exp \left( - \sum_{k=2}^{\log N} 1/(k \log k) \right) \approx \exp(- \log\log\log N) = \frac{1}{\log \log N}$$ 
Thus the probability that a number that passes the test is prime is on the order of
$$ \frac{\log \log N}{\log N} $$
A: The probability that $n$ is not divisible by $p$ is : $1-\frac{1}{p}$, then
The probability that $n$ is prime is :
$$\prod_{\substack{\log_2(n) < p \leq \sqrt{n} \\ \text{p prime}}} \left( 1 - \frac{1}{p} \right)$$
Consider Mertens 3rd theoreme as $n \to +\infty$:
$$\prod_{\substack{p \leq n \\ \text{p prime}}} \left(1-\frac{1}{p}\right) \sim \frac{e^{-\gamma}}{\log(n)}$$
Then :
$$\prod_{\substack{\log_2(n) < p \leq \sqrt{n} \\ \text{p prime}}} \left( 1 - \frac{1}{p} \right) \sim \dfrac{2 \log(\log_2(n))}{\log(n)}$$
