Definition
A recursive set (or decidable set) is a set of natural numbers S such that there exists an algorithm that, given any natural number n, halts in finite time and correctly outputs "yes" if n ∈ S or "no" if n ∉ S. Equivalently: both S and its complement are recursively enumerable.
Why it matters
How it works
To show a set is recursive, exhibit a decision procedure: an algorithm that on any input halts with the correct answer. To show a set is not recursive, reduce a known undecidable problem (often halting) to it. Trial division decides primality. Linear-time arithmetic decides divisibility. The complement of an r.e. set may or may not be r.e.; when it is, both are r.e. and so the original is recursive.