December 13, 2013
This question appears from time to time as an interview question or on the coding-challenge web sites.
Write a function that calculates n! (mod p) when p is prime. Then extend the function to calculate n! (mod m) when m is not prime. Can you calculate the factorials using fewer than n−1 modular multiplications?
For instance, 1000000! (mod 1001001779) is 744950559.