[Solved] How can I work out how long a factorial will take in Python?

by


(This answer is a spin-off of the discussion of modular factorials in the comments.)

Computing modular factorials by taking mods at each step is definitely the way to go and can be used in conjunction with Wilsons’s Theorem to give an (impractical) way to test for primes:

def modFact(k,n):
    #computes k! mod n
    p = 1
    for i in range(1,k+1):
        p = (p*i) % n
    return p

def isPrime(n):
    return n == 1+ modFact(n-1,n)

Typical output:

>>> for i in range(2,20): print(i,isPrime(i))

2 True
3 True
4 False
5 True
6 False
7 True
8 False
9 False
10 False
11 True
12 False
13 True
14 False
15 False
16 False
17 True
18 False
19 True
>>> isPrime(531455)
False
>>> isPrime(531457)
True

solved How can I work out how long a factorial will take in Python?