# What is the chance that a number $P$ is prime if it's not divisible by any number less than $x$?

I am trying to check if a very big number ($$>10^{10,000,000}$$) is possibly prime. I have written a computer program to check if the number has any smallish (less than like $$600,000,000$$) factors... it doesn't. I know that the chance of a random number $$p$$ being prime is $$\dfrac{1}{\ln p}$$, but what if it doesn't have any factors less than $$600,000,000$$? Or more generally, what is the probability that $$p$$ is prime if it doesn't have any factors less than $$x$$?

I thought that it might be $$\dfrac{\ln(x)}{\ln p}$$ but since you only have to check up to the square root of the number to confirm it's prime that didn't make since. I would guess it might be $$\dfrac{\ln(x)^2}{\ln p}$$ but that's just a guess.

Any help is appreciated. Thanks in advance!

• Possibly useful: Dickman function – Brian Tung Aug 28 at 16:48
• @BrianTung To the best of my understanding, that is the chance that all of a number's factors are less than $x$ rather than if all of the factors are bigger than $x$. – Houston Aug 28 at 17:13
• Oh, sorry, you don't want any factors smaller than a given threshold; I misread you. – Brian Tung Aug 28 at 19:58
• In fact, the chance is of the magnitude you expected, just about $1.781$ times larger. See the below answer. – Peter Aug 29 at 11:41

If a huge number has no prime factor below $$n$$ and $$n$$ itself is large (lets say $$10^4$$ or larger) , then the chance that the number is prime increases approximately by the factor $$e^{\gamma}\cdot \ln(n)$$ , so if the trial factor limit is $$\ 10^k\$$ , the factor is about $$\ 4.1\cdot k\$$.

So, the chance for the huge number $$N$$ to be prime is $$\frac{e^{\gamma}\cdot \ln(n)}{\ln(N)}$$

So, even if you check the prime factors upto $$\ 10^{10}\$$ , the chance increases only by a factor $$\ 41\$$. That means that a number with millions of digits still has a very low chance to be prime. This is the reason for the difficulty to find huge primes, trial factoring has a much smaller effect than one would expect.

A bit higher is the chance if you search for prime numbers of a special form, for example mersenne primes because of the form the prime factors must have, but I do not know how large this additional effect is.

• Thank you! The number is of a special form but I just wanted to know if there is a decent chance that it's prime before I did a big computation to actually see if it was, since it you wouldn't know until the computation is complete and you have an answer. – Houston Aug 29 at 19:16