UVa 160

From Algorithmist

Contents 1 160 - Factors and Factorials 2 Summary 3 Explanation 4 Gotcha's 5 Input 6 Output

[edit] 160 - Factors and Factorials

• http://acm.uva.es/p/v1/160.html

[edit] Summary

Bruteforce on all primes up to 100.

[edit] Explanation

Since the upper limit for N is 100, then the largest prime that can divide N! is 97. This is a rather small number, so we can simply walk the list of primes in any old fashion and see how many times it divides into N!. Since N is so small, it is very hard to have a solution time out.

[edit] Gotcha's

N! for N = 100 will not fit into any integral type, you must determine divisibility in another manner.

[edit] Input

2
5
53
100
0

[edit] Output

  2! =  1
  5! =  3  1  1
 53! = 49 23 12  8  4  4  3  2  2  1  1  1  1  1  1
        1
100! = 97 48 24 16  9  7  5  5  4  3  3  2  2  2  2
        1  1  1  1  1  1  1  1  1  1