Product of Two Primes

Date: 10/27/1999 at 10:50:39
From: Rob Amure
Subject: Discrete math problems

How many positive integers less than 100 can be written as the product 
of the first power of two different primes?

Date: 10/28/1999 at 10:33:31
From: Doctor Rob
Subject: Re: Discrete math problems

Thanks for writing to Ask Dr. Math.

First throw out all multiples of 2^2, 3^2, 5^2, and 7^2 (all squares 
of the primes up to sqrt[100] = 10):

     100*(1-1/2^2)*(1-1/3^2)*(1-1/5^2)*(1-1/7^2)

and round down to the nearest integer. Then throw out 1. Then throw 
out the 25 primes smaller than 100. Finally you have to throw out the 
multiples of 2*3*5 = 30, 2*3*7 = 42, 2*3*11 = 66, 2*3*13 = 78, and 
2*5*7 = 70 (all triple-products of distinct primes the result of which 
is < 100), whose number is

       [100/30] + [100/42] + [100/66] + [100/78] + [100/70]
     = 3 + 2 + 1 + 1 + 1
     = 8

Another way to count this would be to use generating functions. Let

    p(x) = x^log(2) + x^log(3) + x^log(5) + x^log(7) + x^log(11) + ...

Then p(x)^2 will have a term x^log(p*q) for every pair of primes 
p and q. To get rid of terms with p = q, subtract p(x^2). Then every 
pair with p < q is matched with a pair with p > q, so to remove 
double-counting, divide the result by 2. Discard all terms with an 
exponent greater than log(100). Then put x = 1, and you'll have your 
result.

Still another way to solve the problem is to use the prime-counting 
function pi(x), which gives you the number of primes less than or 
equal to x. The number of products of p*q with p < q can be split up 
according to the value of p, and p < sqrt(100), so p = 2, 3, 5, or 7 
only. For any p, the number of q's is pi(100/p) - pi(p). Add this up 
for p = 2, 3, 5, and 7, and you'll have the answer.

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/