A positive integer is called cyclic if it is not divisible by the square of any prime, and whenever $p<q$ are primes that divide it, $q$ does not leave a remainder of $1$ when divided by $p$. Compute the number of cyclic numbers less than or equal to $1000$.
Firstly note that a cyclic positive integer $n$ must be squarefree and so has at most $4$ prime factors, since $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 > 1000$. Thus if $n$ has exactly one prime factor $p_1$, there are $\pi(1000)$ such cyclic integers. If $n$ has exactly two prime factors $p_1 < p_2,$ let $p_2 = p_1k+r,$ where $1 < r \leq p-1$. Then $p_1 \leq 29$. But it seems hard to count primes with this property.