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 have no 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 have no 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 e n We can see this by considering the prime factorization. Suppose that k = p p · · · p , with p , . . . , p 1 n 1 2 n e e e 1 2 n primes. Then we can write m = p and n = p · · · p . So, we want to find the powers of primes that 1 2 n are 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 higher powers 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.