Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I want to know the probability that a number is not divisible by any prime smaller than or equal to n. ie, I find a big number, I trial division it up to 300000 and don't find any factors. I want to know how unlikely that sort of event is.

I've tried to juggle around with some formulas in my head, to come up with something, but so far no good. I feel that it should be pretty simple.

Approximal solutions is OK, but please state in your answer whether or not it is an exact formula or a numerical solution.

I know I can calculate it using all the primes smaller than or equal to n $ prob(n) = (p_1-1)/p_1 \times (p_2-1)/p_2 \times (p_3-1)/p_3 ... $

I want a smaller solution that works with all n's, without knowing all the primes below it. I feel the prime number theorem can be used somewere here but I'm not sure how.

People have got to have encountered this problem before. People do primality proving/factoring all the time, and when the number is large enough, there really is no other way to do it than trial division (because the other methods requires one to work modulo the number to be tested, which is too large). Somebody else have got to have tried testing a large number, not found any factors below n, and wanted to know how unlikely that scenario was. I feel there has to be a ready formula, but I cant find any.

Googling and searching on math.stackexchange has yielded nothing for me.

Thanks in advance for any help

share|improve this question
    
A good ref. on precisely this question is J. Stopple, Primer of Analytic Number Thy, Chapter 5. Cambridge Press. "Not having prime factors below n" means "being prime," I would think. The main point is that "being prime" (or not) is determinate. You have to be very careful when speaking of the chance of a number being prime. –  daniel Jan 22 '13 at 21:18

1 Answer 1

I think what you want is Mertens' third theorem:

$$ \lim_{n\to\infty}\log n\prod_{p\le n}\left(1-\frac1p\right)=\mathrm e^{-\gamma} $$

with $\gamma$ the Euler–Mascheroni constant, which implies that your "probability" is asymptotic to

$$ \frac{\mathrm e^{-\gamma}}{\log n}\;. $$

share|improve this answer
    
Maybe worth noting the error is $O(1/(\ln n)^2).$ –  daniel Jan 22 '13 at 22:20

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.