HMMT 十一月 2008 · GEN1 赛 · 第 8 题
HMMT November 2008 — GEN1 Round — Problem 8
题目详情
英文原题
- [ 7 ] How many integers between 2 and 100 inclusive cannot be written as m · n , where m and n haveno common factors and neither m nor n is equal to 1? Note that there are 25 primes less than 100.
解析
英文解析
- [ 7 ] How many integers between 2 and 100 inclusive cannot be written as m · n , where m and n haveno common factors and neither m nor n is equal to 1? Note that there are 25 primes less than 100.
Answer: 35 A number cannot be written in the given form if and only if it is a power of a prime.
e e
1 2 en
We can see this by considering the prime factorization. Suppose that k = p p · · · p , with p , . . . , p
1 n
1 2 ne e
1 2 enprimes. Then we can write m = p and n = p · · · p . So, we want to find the powers of primes that
1 2 nare less than or equal to 100. There are 25 primes, as given in the problem statement. The squares
2 2 2 2 3 3 4 4
of primes are 2 , 3 , 5 , 7 . The cubes of primes are 2 , 3 . The fourth powers of primes are 2 , 3 .
5 6
The fifth powers of primes are 2 , The sixth powers of primes are 2 . There are no seventh or higherpowers of primes between 2 and 100. This adds 10 non-primes to the list, so that in total there are
10 + 25 = 35 such integers.