Primitive Recursive Function

In computability theory, a primitive recursive function is a function that can be computed by a computer program whose loops are all for loops with iteration bounds fixed in advance, and primitive recursive functions form a strict subset of the general recursive functions that are also total functions. They are significant because most of the computable functions studied in number theory, and more generally in mathematics, are primitive recursive, with common examples including addition, division, factorials, exponential functions, and the function that returns the nth prime number; showing that a computable function is primitive recursive can be done by showing that its time complexity is bounded above by a primitive recursive function of the size of the input. Constructing a computable function that is not primitive recursive is notably difficult, though such functions do exist, and the complexity class containing all primitive recursive functions is called PR.