Associated Topics || Dr. Math Home || Search Dr. Math

### 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/
```
Associated Topics:
College Discrete Math
College Number Theory
High School Discrete Mathematics
High School Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search