Quote Originally Posted by tonberrian View Post
You should start off with Is it Prime? first. If Yes, you don't have to ask about factors, and if No, you don't have to ask Is it 2? Also, you need to ask Is it 1 before any prime search.

Edit: And Is it 0?
Or just add "is it composite" after "is it prime."

Of course, "yes" to the first reduces the remainder to ∞ possibilities, "yes" to the second similarly leaves with you only ∞ possibilities, and the odds of it being 1 or 0 are 1 in ∞. But hey, if both those trigger a "no," go you!