I have just completed an exercise from my textbook which wanted me to write a program to check if a number is prime or not.

I have tested it and seems to work fine, but how can I be certain that it will work for every prime number?

public boolean isPrime(int n)
       int divisor = 2;
       int limit = n-1 ; 

            if (n == 2)
                return true;
                int mod = 0;
                while (divisor <= limit)
                      mod = n % divisor;
                      if (mod == 0)
                          return false;

                if (mod > 0)
                    return true;

      return false;

Note that this question is not a duplicate of Theoretically Bug Free Programs because that question asks about whether one can write bug free programs in the face of the the limitative results such as Turing's proof of the incomputability of halting, Rice's theorem and Godel's incompleteness theorems. This question asks how a program can be shown to be bug free.

  • You can reduce some of your if statements. gist.github.com/thinkingmedia/210072f01d6235c57174
    – Reactgular
    Jun 2, 2014 at 14:13
  • 5
    It is not clear if you are asking about programs in general, or about this particular program. If the former is the case, then your question is a duplicate. If the latter is correct, you should better post your code at codereview.stackexchange.com
    – Doc Brown
    Jun 2, 2014 at 14:30
  • 2
    Re: duplication. The question programmers.stackexchange.com/questions/239210/… asks whether or not Turing's, Gödel's and Rice's theorems imply that all programs have bugs. That is a yes/no question. This question seems to ask how can we show that a program is flawless. This is a different question. Jun 2, 2014 at 15:27
  • 1
    @TheodoreNorvell agreed, but more specifically he's asking how do you verify an algorithm of infinite possible outcomes without performing all infinite outcomes. I think an answer about branch complexity and algorithm testing would be right on.
    – Reactgular
    Jun 2, 2014 at 15:30
  • That's easy. Write a cheque.
    – JensG
    Jun 2, 2014 at 20:16

3 Answers 3


You cannot establish correctness via testing. All that tests tell you is that the system responds correctly to the cases you exercised. (Even if there is a finite number of possible inputs, that is not enough, because strictly speaking, the test only tells you that the system responded correctly in this instance - it might be secretly non-deterministic, and you'd never know.)

To establish that your code is indeed correct for all possible inputs, verification is required. It amounts to a mathematical proof that the transformation that your code embodies is indeed the correct one for the specified problem.

Verification is perfectly possible, particularly for mathematical tasks, but usually not worth the added effort. Particularly, making sure that your requirement does indeed state what it seems to state and your code does indeed define what it seems to define is surprisingly difficult and hairy when all details of a real programming language, platform, standard library etc. are properly considered. That is why verification is not encountered in practice as much as copious amounts of regression tests.

  • A verification does not confirm that your program is correct unless you can show that your verification is correct. And by the curry-howard isomorphism, in the general case this is equivalent to proving a program is correct. What you can do is reduce the correctness problem to an easier correctness problem, or one you already have confidence in. In short, verification is perfectly impossible, except for all practical purposes it is merely difficult.
    – Yakk
    Jun 2, 2014 at 15:48
  • You can reduce a correctness problem to problems that are not (in any ordinary sense) correctness problems. Hoare logic shows how to reduce correctness problems to problems of first order logic. Jun 2, 2014 at 16:50

There are a number of frameworks for proving that code is correct. You can read about some of them in books such as

For your program, I'll assume that you don't care about negative n and that you can handle the n==0, n==1, and n==2 cases without any help; I'll only look at the case where n>2.

The key is to note that (in cases where n > 2) every time the loop's guard expression divisor <= limit is evaluated, the following 5 facts are true of the program's state:

n % i != 0, for all i from 2 up to, but not including divisor
limit == n-1
2 <= divisor && divisor <= n
mod != 0 || divisor == 2
n is the same as the argument  // i.e. n hasn't been changed

These 5 facts are called the loop's invariant. To trust that the loop's invariant holds where I said it does, you can check

  • that it holds the first time the guard is evaluated and
  • that, if the invariant is true and the guard is true, then one execution of the loop's body will leave the program in a state where the invariant is true again.

Therefore, when and if the loop terminates normally*, all the above are true and so is divisor > limit. This tells you that divisor == n and so you have

n % i != 0, for all i from 2 up to, but not including n
mod != 0
n is the same as the argument // i.e. n hasn't been changed

Therefor, if the loop terminate normally, the return true after the loop will be executed and the argument is prime.

The only cases left to worry about are those where the loop does not terminate normally. There are two reasons a loop might not terminate normally: it is infinite or there is a jump out of it, such as a break, return, or exception. In your code, the loop can be shown not to be infinite and the only jump out is when n % divisor == 0. Since, at that point, we also have

2 <= divisor       // from the invariant
divisor <= limit   // from the guard
limit == n-1       // from the invariant

we have 2<=divisor && divisor < n. So if the return false in the loop is executed, it is only when n % divisor == 0 and divisor is greater than 1 and less than n, and so the n (and hence the argument) is not prime.

In summary

  • for nonprimes (greater than 2), the loop can not terminate normally and so the return false must be executed, and
  • for primes (greater than 2) the loop must terminate normally and in a state where mod != 0 and so the return true will be executed.

The proof suggests a few ways you could make the code simpler. The books I mentioned provide ways to make the analysis more formal, although I think only Hehner's provides a way to deal with early exits from loops.

[*] By "terminates normally", I mean that it terminates because its guard evaluates to false.

Does this analysis give you absolute certainty that you code is flawless? I hope not. But it should give you reassurance. One can use tools such as ESC/Java2 or Spec# so that a computer can check that one hasn't made any mistakes. That would raise the level of trust that the code is right to a very high level. Of course there could be bugs in the program one uses to check the verification or in the hardware it runs on. For practical purposes code such as yours can be verified and the verification can be checked by carefully written and trustworthy tools.

  • +1 for rigor and for not hand-waving the issue with "there's always bugs" or "it's not possible".
    – Doval
    Jun 2, 2014 at 18:00
  • That rigor is nice at the academia but as Killian noted it don't work on pratical day-by-day basis. There are two big problems: 1) Try to prove a small program is correct. It ill take more effort than write the program itself. Also try to make the slightest change in requirements and all that proof-work must be re-done. 2) The proof ill not consider a few "details" like wrong input (hey I inputed a negative number or a fraction or even a non-numeric one!) transactions, browser (in)compatiblity, security, etc. All things a good programmer must consider.
    – jean
    Jun 3, 2014 at 11:22
  • @jean I was just answering the question as it was asked: "How can I be certain my code is flawless?" You are bringing up a whole other set of questions such as "Is it practical on a day-to-day basis to verify my code?", "What if the computer (or part of the computer) fails when my 'flawless' routine is half-way done?", "What if requirements change after I've verified my code?", and "What if the compiler or interpreter is flawed?" Great questions. Important questions. On negative inputs: I dealt with them in my answer. On fractional & nonnumeric inputs: not an issue as the parameter is int. Jun 3, 2014 at 14:35

For something like prime numbers, you will never be sure that it will work for all primes, because the set of all prime numbers is infinitely long, and therefore you'd never stop coding your unit test. That being said, there's many different ways to judge the quality of code, and passing a unit test is only one of them. For example, if you're building a piece of code to find all the primes in the world, your solution will probably work fine for lower numbers, but as the size of the numbers gets larger, you will exceed the size of int, which means you've got one small limitation in your program. Also, performance will degrade as the numbers get bigger and your loop takes longer.

One other small point, negative numbers can't be prime, so instead of int, you could use unsigned int, or unsigned long to extend the range of numbers you can verify.

In your case though, what you're doing is focusing on the wrong thing. No code is ever flawless. There will always be bugs. Does it meet the requirements you have set before you? Does it perform adequately well for your needs?

Then you're good.

  • 4
    Fun fact: One can test for all primes that fit into int. It's not even a lot, there are "only" about 2^31/ln(2^31) ~= 10 million prime numbers smaller than INT_MAX.
    – user7043
    Jun 2, 2014 at 14:21
  • Well sure. If you're only looking for all the primes less than INT_MAX this code would be fine. I was just thinking ahead beyond that limit because the poster asked about being flawless. Something like checking for prime numbers extends well beyond that limit, and if you're really concerned about empirical flawlessness, then you need to consider that case. I love math programming. I was just playing around with a program to output prime numbers to show my daughter how programming works. Jun 2, 2014 at 14:30
  • 2
    You are assuming that unit testing is the only option, ignoring verification. Jun 2, 2014 at 16:51
  • True. There are other ways beyond unit testing to verify code. Jun 3, 2014 at 1:31

Not the answer you're looking for? Browse other questions tagged or ask your own question.