Is there an easy way to compute the following question:

How many numbers of the form $p_1^2 p_2 p_3$ are there less than $10^{15}$ for $p_1$, $p_2$, $p_3$ distinct primes?

The only thing that strikes me as a possibility is iterating through the various primes and finding the number of primes such that $2^2 3 p_3<10^{15}$, etc, which would give me


But that gets me no where fast. I'm mostly looking for "Is there an easy way to do this?" and hints at what it might be, I'm not actually looking for it to be solved for me, just a push in the right direction.

My other issue is that my primepi function I have written in python doesn't really support going up this high... I end up having to turn to wolfram alpha to get many of the values and that is no way to make an automated computation.

  • $\begingroup$ Do you need an exact answer or a good approximation? $\endgroup$ Apr 9, 2012 at 1:39
  • $\begingroup$ Exact. It'll need to work with other power combinations. It doesn't necessarily have to be able to go up to 10^{15}, but the higher I can get an exact answer the better. $\endgroup$
    – Dan
    Apr 9, 2012 at 4:26
  • 3
    $\begingroup$ Getting an exact count can't be any easier than getting an exact count of the number of primes up to $10^{15}/12$, so you may be asking for too much. $\endgroup$ Apr 12, 2012 at 5:45

1 Answer 1


This Wolfram's Mathematica code gives the answer, but it will take ages for calculating up to $10^{15}$. The variable MAX is the upper limit.

MAX = 10^3;
count = 0;
For[n = 1, n < MAX, n++,
    array = FactorInteger[n];    (* factorizes N in a product of prime powers *)
    If[Length[array] == 3,       (* if N is composed by exactly 3 primes *)
        If[Or[                   (* then it will check their exponents *)
            And[array[[1]][[2]] == 2, array[[2]][[2]] == 1, array[[3]][[2]] == 1],
            And[array[[1]][[2]] == 1, array[[2]][[2]] == 2, array[[3]][[2]] == 1],
            And[array[[1]][[2]] == 1, array[[2]][[2]] == 1, array[[3]][[2]] == 2]
             ], (* if the exponents are (2,1,1) or (1,2,1) or (1,1,2) *)
            count++   (* then it increases the count variable *)

I've tested it up to $10^{9}$ and got exactly $68391432$ numbers.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .