UVa 160

From Algorithmist
Jump to navigation Jump to search

160 - Factors and Factorials[edit]

Summary[edit]

Bruteforce on all primes up to 100.

Explanation[edit]

    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.

Gotcha's[edit]

N! for N = 100 will not fit into any integral type, you must determine divisibility in another manner. And also be cautious that you are not printing a newline when factors size in 15.

Input[edit]

2
5
53
100
0

Output[edit]

  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

Solutions[edit]