Prime Numbers...

Question

Are there any functions whose output is a prime number?
For eg. The function $x^2$ spits out squares of $x$; is there a similar function for Prime Numbers as well(which gives output as Prime Numbers)?

Answer 1

A function is, in essence, is a well-defined rule.

Do prime numbers follow a well-defined rule? No.

So, there can't be a function whose output is a prime number , atleast not one which can be written out algebraically ( you could define a function however; for example you can define a function f(n) = n iff Φ(n) = n-1 and so on. Φ(N) here denotes the totient function)

You can have a function which gives primes for atleast some values of n algebraically ( i.e. with a restricted domain ) e.g. p(n) = ${n^2+n+41}$ which gives primes for inputs upto 39, but fails at 40.

Edit 1: By algebraically, I mean not by using simple/elementary operations, i.e. not in the form of a polynomial.

Edit 2: By algebraically, I mean not by using simple/elementary operations, i.e. not in the form of a finite polynomial.

Answer 2

A simple function is

${\displaystyle f(n)=\left\lfloor {\frac {n!{\bmod {(}}n+1)}{n}}\right\rfloor (n-1)+2}$

(for positive integer n, where ${\displaystyle \lfloor \ \rfloor }$ is the floor function, which rounds down to the nearest integer.)

Proof-By Wilson's theorem, +1 is prime if and only if ${\displaystyle n!\equiv n{\pmod {n+1}}}$. Thus, when n+1 is prime, the first factor in the product becomes one, and the formula produces the prime number n+1. But when n+1 is not prime, the first factor becomes zero and the formula produces the prime number 2.

Answer 3

Conway's prime algortihm (see also) finds all primes using a "simple" rule if I am not mistaken.