Probability that n is a semi-prime or prime
 

What is the probability than for any integer n, n is a semi-prime (a semi-prime is a numbers which has only 3 or 4 positive divisors, or two prime factors) or a prime (numbers which only has divisors 1 and n)?

Hint: Who on this forum doesn't know the probability n is prime is roughly 1/log(n)? :smile:

[QUOTE=carpetpool;451045]What is the probability than for any integer n, n is a semi-prime (a semi-prime is a numbers which has only 3 or 4 positive divisors, or two prime factors) or a prime (numbers which only has divisors 1 and n)?

Hint: Who on this forum doesn't know the probability n is prime is roughly 1/log(n)? :smile:[/QUOTE]

3 denotes a prime square and only has one distinct prime factor.

[QUOTE=science_man_88;451050]3 denotes a prime square and only has one distinct prime factor.[/QUOTE]

Yes, but the problem to answering this question with the probability a number is prime is equivalent to factoring n, which is most likely not possible as of today.

[QUOTE=carpetpool;451051]Yes, but the problem to answering this question with the probability a number is prime is equivalent to factoring n, which is most likely not possible as of today.[/QUOTE]

in fact even the 4 divisor case has a subset where n is a prime cube. also ceil(log_2(n)) is the highest number of factors any n can have ceil(log(3)) if it's odd. then you can reduce the problem to how many ways can you arrange the exponents of the primes in the factorization of a number such that it has a specific number of divisors versus how many partitions of numbers s<ceil(log(3)) there are in total. so up to certain values it is potentially easily figurable. you can figure out the number of divisors of a number by the product of the exponent +1 for each exponent given. edit: okay replace ceil with floor but you get the point I hope.

[QUOTE=carpetpool;451045]What is the probability than for any integer n, n is a semi-prime (a semi-prime is a numbers which has only 3 or 4 positive divisors, or two prime factors) or a prime (numbers which only has divisors 1 and n)?[/QUOTE]

Asymptotically, log log n/log n.

[QUOTE=CRGreathouse;451072]Asymptotically, log log n/log n.[/QUOTE]

How do you interpret that?

I am assuming (log (log n))/(log n). Right?

For what it's worth:

The first Mersenne number with no known factors is M1277 (or M1207 if we count non-prime exponents, but I don't think this is a semi-prime candidate).

There are 14 Mersenne primes smaller than this, and 42 Mersenne semi-primes (OEIS sequence [URL="http://oeis.org/A085724"]A085724[/URL]). The latter set includes M4, M9 and M49 which have non-prime exponents.

Here is [URL="http://www.mersenneforum.org/showthread.php?t=14249"]an old thread about Mersenne semi-primes[/URL].

[QUOTE=carpetpool;451075]How do you interpret that?

I am assuming (log (log n))/(log n). Right?[/QUOTE]

A trivial google search yields [url=https://en.wikipedia.org/wiki/Talk%3ASemiprime#Probability]semiprime probability[/url] with "log(log(n))/log(n) + O(1/log(n))" shown. It links to a more complicated mathoverflow discussion.

The comments about factoring seem to be about trying to give a correct answer for a specific [i]n[/i]. Remember that primality is much simpler than factorization in complexity (and in practice). This is also a help if we do find a single factor, in that we can reasonably see whether the remainder is composite. While we don't need a full factorization, as [i]n[/i] gets very large I'm not sure that helps much with complexity.

[QUOTE=carpetpool;451075]How do you interpret that?

I am assuming (log (log n))/(log n). Right?[/QUOTE]

Yes -- I'm not sure how else one could interpret it. :ermm:

Also, here (as usual) log means base e.

[QUOTE=danaj;451095]A trivial google search yields [url=https://en.wikipedia.org/wiki/Talk%3ASemiprime#Probability]semiprime probability[/url] with "log(log(n))/log(n) + O(1/log(n))" shown. It links to a more complicated mathoverflow discussion.[/QUOTE]

Yes, that's my MathOverflow question!

[QUOTE=danaj;451095]Remember that primality is much simpler than factorization in complexity (and in practice). This is also a help if we do find a single factor, in that we can reasonably see whether the remainder is composite. While we don't need a full factorization, as [i]n[/i] gets very large I'm not sure that helps much with complexity.[/QUOTE]

Right, this is how [url=https://github.com/CRGreathouse/PARI-extensions/blob/69c72d1c6da659ad92966c28a37e5c24be1c4e31/prime.gp.c#L6]I do it/[url], I don't know of a better way. For random numbers this works decently with SQUFOF + ECM (there is often a small factor you can pull out). For large hard numbers it's infeasible as you suggest, nothing easier than NFS.

Ah, I had seen you wrote an answer, but missed that it was your question!

I thought the link gave a little more explanation for the OP, including more detail for someone to read if they were curious.

Thanks for the code link. Now you're making me think about implementing it, not because I have anything useful to add, but because it looks like a fun bit of optimization for smaller inputs. For larger ones, yes -- some heuristics trying to weed out easier results common with random inputs, but for the harder ones there's not an easy answer.