Probability with primes

Suppose we're picking an integer \(\displaystyle x\) at random between 1 and, let's say, 100. And suppose we want to know the probability that \(\displaystyle x\) has \(\displaystyle k\) prime factors (\(\displaystyle k \geq 1\)).

We'd need to know how many of the integers between 1 and 100 have a single prime factor (i.e. the primes themselves), and also how many have 2 prime factors, how many have 3 primes factors, etc.

I'm wondering if there's a way to be more efficient than actually checking each of the 100 possible integers for its number of prime factors?

Thanks in advance for any thoughts!

Stochastic_Jimmy said:

Suppose we're picking an integer \(\displaystyle x\) at random between 1 and, let's say, 100. And suppose we want to know the probability that \(\displaystyle x\) has \(\displaystyle k\) prime factors (\(\displaystyle k \geq 1\)).

We'd need to know how many of the integers between 1 and 100 have a single prime factor (i.e. the primes themselves), and also how many have 2 prime factors, how many have 3 primes factors, etc.

I'm wondering if there's a way to be more efficient than actually checking each of the 100 possible integers for its number of prime factors?

Thanks in advance for any thoughts!

Click to expand...

I think I would write a program, with Nmax as a parameter. How do you want to handle repeated factors .. for instance, 8 = 2^3, Do you call that 1 prime factor, or 3?
And is the number 1 special, with NO prime factors (as pure mathematicians define primes)?

I would define arrays N_primes (initialized to 1) and Remainder (initialized to N).
Have a list of all primes P < sqrt(Nmax), then loop N from P to Nmax step P, incrementing N_primes(N) and dividing Remainder(N) by P.

After doing that for P=2,3,5,7 (assuming Nmax=100, this is all you need), deal with the Remainder array to account for repeated factors. Perhaps a way to do that is to add N_primes(Remainder(N)) to N_primes(N) -- that would have to be thought about!

Thanks a lot for the responses! Much appreciated.