I don't think you can do any mathematics at all without axioms, or principles which are equivalent to axioms.
Consider the statement "3 is prime". There are two definitions embedded here:
The notion of the 'successor' is usually supplied by some axiom scheme such as Peano Arithmetic, in order to assert that there exists the integer zero, and a successor to any integer. Even if we set that aside, how do you propose to obtain an exhaustive search of all of the integers for possible divisors of 3, to ensure that there are exactly two such divisors? In practise, we reduce the search space to the integers 1, 2, and 3, because we may prove that multiplication has certain properties of monotonicity with respect to the total order defined on the integers by extending a < a+1 transitively. This is as much axiomatic as the sort of reasoning that allows us to infer that any finite list of primes is incomplete.
Conversely, because we may reason axiomatically to obtain a procedure of bounded length to find the divisors of any positive integer, we can also reason axiomatically to obtain an algorithm which is guaranteed to halt (and with a bound on its running time) for any list of primes a further prime which is not contained in the list. The fact that we cannot demonstrate by exhaustion that every prime is smaller than some prime afterward, is not any more problematic than the fact that we cannot demonstrate by exhaustion that any of the integers larger than three can be a divisor; they are the same sort of statement.
Generally, the only reason why any sort of "numerical experiment" could be used to ascertain any facts at all beyond mere existence theorems is because we adopt principles, either axiomatic or intuitive (that is, pre-axiomatic), which allow us to infer certain consequences from an investigation of only a finite search space. For instance, by investigation of a finite search space, we may show that 3 has at least two factors; but to show that it has no more is a universal statement, not an existential one, and so requires axioms which allow us to infer universal statements. And without principles which assert the existence of certain objects, even existence theorems cannot be proven.