Of course you can. Each time you prove that an integer is a prime number you prove a negative.
The way this question more recently has been discussed is in terms of whether the search space is finite or not.
Amos has posted a wonderful example in which the search space is finite at this moment in time but infinite when you consider all future moments in time. The obvious solution is to think of an example in which the search space is also finite if you look at all future times. Prime numbers are just one such example. There are many more such examples in mathematics.

Wolfgang