# Probability to find a prime factor?

Suppose I have been given positive numbers $n,m$, $n<m$, and an integer $N$. What is the probability that $N$ has a prime factor between $[n,m]$? I have heard about the prime number theorem but I'm not sure how can I apply it to this problem if I can apply it at all.

• If $N<n$ then the probability is zero. – Dietrich Burde Sep 6 '14 at 20:52
• That depends on the distribution of $N$. – JimmyK4542 Sep 6 '14 at 20:58
• This question is not going to have a nice answer. Do you really need to pose it in such generality? There might be some hope of answering a much more restricted question, like how many 200 digit numbers are not prime but have no factors of less than 90 digits (highly relevant to cryptography). – almagest Sep 6 '14 at 21:26
• I decided to put the question in general form to see how much we can achieve results like that. Originally I would like to know what is the probability that the general number field sieve would find a new factor to $2^{2^{12}}+1$. – guest Sep 7 '14 at 7:48

If $N$ is large compared to $m$, and $n>2$ is not too near to $m$, then the number of primes is asymptotically expected to be $$\sum_{n\le p\le m}\frac1p\sim\log\log m-\log\log n.$$
You can treat finding a factor as a Poisson event, making your chance of finding a factor in that range approximately $$1-\exp(-(\log\log m-\log\log n))=1-\log n/\log m.$$
• This looks more like the expected number of prime factors in that range that divide N. The probability should be about $1-\prod_{n\leq p\leq m} \left( 1-\frac{1}{p} \right)$, shouldn't it? – Michael Stocker Sep 30 '14 at 11:28