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 = 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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.