Proof: By Euclid
(related to Proposition: 7.32: Natural Number is Prime or has Prime Factor)
 In fact, if $A$ is prime then that which was prescribed has happened.
 And if (it is) composite then some prime number will measure it [Prop. 7.31].
 Thus, every number is either prime or is measured by some prime number.
 (Which is) the very thing it was required to show.
∎
Thank you to the contributors under CC BYSA 4.0!
 Github:

 nonGithub:
 @Fitzpatrick
References
Adapted from (subject to copyright, with kind permission)
 Fitzpatrick, Richard: Euclid's "Elements of Geometry"