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.
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.