Fool algorithm for finding prime numbers based on long arithmetic

We will observe the trivial and probably the shortest (but not fast) algorithm for finding all prime numbers $$$p \in \mathbb{N}: p \leq n$$$ based on Wilson's theorem and long arithmetic.

1. Wilson's theorem

Algorithm based on well-known in number theory Wilson's theorem. Often implication is being proved only from left to right but it is important to prove equivalence.

Theorem (Wilson).

$$$p \in \mathbb{N}: p \ge 2$$$ is prime if and only if $$$(p-1)! \equiv -1 \pmod{p}.$$$

Proof.

$$$\rightarrow \quad$$$ p is prime so $$$\forall$$$ a $$$\in \mathbb{Z}/p\mathbb{Z}$$$ $$$\quad$$$ $$$\exists a^{-1} \in \mathbb{Z}/p\mathbb{Z}: a\cdot{a^{-1}}=1$$$. Therefore in product $$$1 \cdot 2 \cdot \dotso \cdot (p-1)$$$ all elements are divided in pairs $$$(a, b)$$$ such that $$$ab=1$$$.
$$$\leftarrow$$$ $$$\quad$$$ Let's assume that p is composite. If p is not full square: $$$p \neq a^2 \quad \forall a \in \mathbb{Z}$$$ then $$$\exists a,b \in \mathbb{N}: a,b < p$$$ and $$$ab=p$$$ so $$$p=ab$$$ divides $$$(p-1)!$$$. Else if $$$p=a^2: a>1$$$ then a divides $$$gcd(p, (p-1)!)$$$ so a divides $$$(p-1)!$$$ mod $$$p$$$ and as a result: $$$(p-1)! \not\equiv -1 \pmod{p}$$$ — contradiction.

2. Algorithm

From Wilson's theorem can be derived very simple algorithm for finding prime numbers.

a = 1
for i in range(2, n):
    if a%i == i-1:
        pass #prime
    a *= i

3. Long arithmetic

It is easy to notice that algorithm needs long arithmetic because factorial grows very fast. The one of fastest implementations of long arithmetic uses FFT (Fast Fourier Transform) for numbers (or polynomials) multiplication. FFT multiplies $$$a\cdot{b}$$$ in $$$O(n\log{n})$$$ where n is max bit-length of a and b. We will use this fact in analysis. P.S. FFT with heuristics is used in Python too.

4. Asymptotic

Notice that at iteration $$$k$$$ $$$a$$$ length is $$$O(\log{k!})$$$ so entire complexity is $$$O(\sum_{k=2}^n{\log{k!}\cdot{\log{\log{k!}}})}$$$

Statement.

$$$\sum_{k=2}^n{\log{k!}\cdot{\log{\log}k!}} = O(n^2\log^2{n})$$$

Proof.

Using Stirling's formula for gamma function (factorial) logarithm

we get:

Using fact $$$\log{(f + o(f))} = \log{f} + o(\log{f})$$$ (can be clearly checked according to the L'Hospital rule) we get that the sum asymptotically equals to:

There is Euler-Maclaurin's summation formula $$$\sum_{k=a}^b{f(k)} = \int_a^b{f(x)dx} + O(f)$$$ for class functions $$$f$$$ such that $$$f'(x) = O(f)$$$ or $$$f'(x) = o(f)$$$. So we can approximate discrete sum with integral:

After applying integration by parts two times we get that value of this integral is $$$O(n^2\log^2{n})$$$, Q.E.D.

5. Conclusion

This algorithm is rather absurd but it shows some simple techniques in work with long arithmetic.