How to express "$n$ is a power of prime" as a logical formula without using exponential notation?

Question

This is a problem, which I encountered while self-studying discrete mathematics from MIT:

Express each of the following predicates and propositions in formal logic notation. The domain of discourse is the nonnegative integers, $\Bbb N$.

Moreover, in addition to the propositional operators, variables and quantifiers, you may define predicates using addition, multiplication, and equality symbols, and nonnegative integer con- stants ($0, 1, ...$), but no exponentiation (like $x^y$).

For example, the predicate “$n$ is an even number” could be defined by either of the following formulas:

$\exists m.(2m= n )$ or alternatively $\exists m.(m+m = n )$

(a) $m$ is a divisor of $n$.

(b) $n$ is a prime number.

(c) $n$ is a power of a prime.

---

Now,

I've got (a) and (b) already, but need some help with (c).

(a) $\exists m\exists p. (mp=n)$

(b) $ ISPrime(n) ::= $(n > 1)$ ∧ \neg (\exists x \exists y. (x \gt 1 \land y \gt 1 \land (x.y=n) )) $

(c) ?

It may have been easier to express that $n$ is a product of two distinct primes. But, here I am struggling to express a recursive relation which is "$n$ is a power of a prime".

$n$ can only be obtained by multiplying $p$ with itself $k$ times (where $k$ in a non negative integer), but this has to be expressed without using exponential notation (a constraint imposed in the question). I could potentially reuse $ISPrime(p)$ from (b), but how?

Update:

Solution to (b) was corrected to account for a comment.

Answer 1

If you have IsPrime then you can say that n is a multiple of at most one prime.

Answer 2

Try expressing a unique feature of prime-powers. Here's my take:

Prime-Power(x) == 'There is a P such that: (a) P is prime; (b) If y divides x, then either y=1 or P divides y'. [formalize in your favorite notation]

(reason it out)