$G\le S_n$ in which all $g\ne e$ have $<\sqrt{n}$ cycles must be $\Bbb Z_p$ or $\Bbb Z_p\rtimes\Bbb Z_q$ Exercise 1.4.18 in Dixon & Mortimer's Permutation Groups is

Let $G$ be a permutation group of degree $n$, and suppose that each $x\ne1$ in $G$ has at most $k$ cycles. If $n>k^2$, show that $G$ acts faithfully on each of its orbits, and that these orbits all have prime lengths. Hence show that $G$ is either cyclic of prime order or non-abelian of order $pq$ for distinct primes $p$ and $q$.
[Hint: Show that $p^2>n$ for each prime $p$ dividing $|G|$.]

The online errata clarifies it should read

"on each of its orbits of length $>1$."


I am almost done. First, suppose a prime $p$ divides $|G|$, then by Cauchy's there is an element $g\in G$ of order $p$. Say it has $c_1$ fixed points and $c_p$ $p$-cycles, so we have the system
$$ \begin{cases} c_1+pc_p = n \\ c_1+c_p <\sqrt{n} \end{cases} $$
Subtracting the first equation from $p$ times the second gives $(p-1)c_1<p\sqrt{n}-n$. The LHS must be nonnegative, so the RHS is positive, so $p>\sqrt{n}$. This gives us the hint.
Second, for the sake of contradiction suppose an orbit wasn't faithful, i.e. there is a nontrivial $g\in G$ which fixes a nontrivial orbit pointwise. The orbit's size is a nontrivial divisor of $|G|$, which must be $\ge$ a prime factor $p$ of $|G|$ (by orbit-stabilizer), which means $g$ has $p$ or more cycles, but $p>\sqrt{n}$ and we assume $g$ must have $<\sqrt{n}$ cycles, a contradiction.
Third, note if $p,q$ are are distinct primes dividing $|G|$, then $p,q>\sqrt{n}$ imply $pq>n$. Every orbit's size is a divisor of $|G|$, but if any nontrivial orbit weren't prime length we'd get a contradiction from $pq>n$ or $p^2>n$ (since the orbit size is bounded above by $n$). After this I started deriving some facts not hinted at to see what I could get.

Fourth, suppose $g\in G$ has prime power order for some prime $p$. If any cycle had length other than $1$ or $p$ then $n>p^2$, a contradiction, so any nontrivial element has prime order.
Fifth, let $p$ be the largest prime divisor of $|G|$ and $g$ an element of order $p$. If there were an orbit of prime-length other than $p$, then $g$ would have to act trivially on it, contradicting faithfulness, so all nontrivial orbits have length $p$.
Sixth, picking a particular orbit of length $p$, we can identify $G$ with a subgroup of $S_p$, which shows any $p$-Sylow is $\cong\mathbb{Z}_p$.
I assume we can show the Sylow subgroup is unique, hence normal, then $G$ normalizes it so it's a subgroup of $\mathbb{Z}_p\rtimes\mathbb{Z}_p^\times$, but I've kind of run out of steam for the moment and don't see how to finish.
 A: This exercise occurs very early in  the book, so it must be possible to solve it without knowing much about permutation groups.
There is a result that says that, if $G$ is a transitive permutation group on $\Omega$, $\alpha \in \Omega$, and $Q \in {\rm Syl}_q(G_\alpha)$ for some prime $q$, then $N_G(Q)$ acts transitively on the fixed point set of $Q$ (which can be proved using the conjugacy part of Sylow' theorem), and I think I can see how to finish the proof by using that result.
Let $q \ne p$ be a prime dividing $|G|$ and $Q \in {\rm Syl}_q(G)$. Then $Q$ must have fixed points in each orbit of $G$, so $N_G(Q)$ acts transitively on its fixed point set in each orbit.
Suppose that $Q$ fixes more than one point of some orbit $\Delta$ of $G$. Now  $Q$ fixes fewer than $\sqrt{n}$ points altogether, or else we would violate the $n > k^2$ condition for elements of $Q$. But then, since $N_G(Q)$ acts transitively on its fixed point set in $\Delta$, $N_G(Q)$ would be divisible by a prime less than $\sqrt{n}$ giving a contradiction.
So $Q$ fixes a unique point in each $G$-orbit, and hence no non-identity element fixes more than one point in any $G$-orbit.
If the claimed result is false, then $|G|$ is divisible by $pqr$ for some prime $r \ne p$ (possibly $r=q$). But then, since no non-identity element fixes more than one point in each orbit, we have $qr$ divides $p-1$, so at least one of $q$ and $r$ is less than $\sqrt{p}$, a contradiction.
