HMMT 二月 2022 · ALGNT 赛 · 第 2 题

HMMT February 2022 — ALGNT Round — Problem 2

Compute the number of positive integers that divide at least two of the integers in the set 1 2 3 4 5 6 7 8 9 10 { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 } . 1

解析

Compute the number of positive integers that divide at least two of the integers in the set 1 2 3 4 5 6 7 8 9 10 { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 } . Proposed by: Daniel Zhu Answer: 22 Solution: For a positive integer n , let rad n be the product of the distinct prime factors of n . Observe m that if n | m , all prime factors of n must divide m , so rad n | m . Therefore, if n is such an integer, rad n must divide at least two of the numbers in { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 } , implying that rad n is either 1, 2, 3, or 5. These have 1, 10, 6, and 5 cases, respectively, for a total of 22. 1