Problem

Source: Brazil National Olympiad Junior 2021 #4

Tags: number theory



Let $d(n)$ be the quantity of positive divisors of $n$, for example $d(1)=1,d(2)=2,d(10)=4$. The size of $n$ is $k$ if $k$ is the least positive integer, such that $d^k(n)=2$. Note that $d^s(n)=d(d^{s-1}(n))$. a) How many numbers in the interval $[3,1000]$ have size $2$ ? b) Determine the greatest size of a number in the interval $[3,1000]$.