20170116, 17:34  #1 
"Sam"
Nov 2016
335_{10} Posts 
Probability that n is a semiprime or prime
What is the probability than for any integer n, n is a semiprime (a semiprime 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)? 
20170116, 18:14  #2  
"Forget I exist"
Jul 2009
Dartmouth NS
10000100000010_{2} Posts 
Quote:


20170116, 18:20  #3 
"Sam"
Nov 2016
5×67 Posts 

20170116, 18:29  #4 
"Forget I exist"
Jul 2009
Dartmouth NS
2×5^{2}×13^{2} Posts 
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.
Last fiddled with by science_man_88 on 20170116 at 18:42 
20170116, 22:59  #5 
Aug 2006
2^{2}·3·499 Posts 

20170117, 00:52  #6 
"Sam"
Nov 2016
5×67 Posts 

20170117, 09:01  #7 
Sep 2003
2·5·7·37 Posts 
For what it's worth:
The first Mersenne number with no known factors is M1277 (or M1207 if we count nonprime exponents, but I don't think this is a semiprime candidate). There are 14 Mersenne primes smaller than this, and 42 Mersenne semiprimes (OEIS sequence A085724). The latter set includes M4, M9 and M49 which have nonprime exponents. Here is an old thread about Mersenne semiprimes. 
20170117, 11:11  #8  
"Dana Jacobsen"
Feb 2011
Bangkok, TH
1110001110_{2} Posts 
Quote:
The comments about factoring seem to be about trying to give a correct answer for a specific n. 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 n gets very large I'm not sure that helps much with complexity. 

20170117, 16:38  #9 
Aug 2006
2^{2}·3·499 Posts 

20170117, 16:45  #10  
Aug 2006
2^{2}·3·499 Posts 
Quote:
Quote:


20170117, 23:45  #11 
"Dana Jacobsen"
Feb 2011
Bangkok, TH
2·5·7·13 Posts 
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. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Semiprime factorization conjecture  Alberico Lepore  Alberico Lepore  7  20180216 08:27 
Probability that n is a prime power  carpetpool  Miscellaneous Math  6  20170130 02:54 
probability a number is prime with a weighted k.  Trilo  Homework Help  12  20140606 19:17 
Probability of a Mersenne number being prime  vimil  Information & Answers  13  20071212 11:21 
probability of finding a Mersenne prime  optim  Math  2  20031206 19:03 