DWITE '11 R4 #2 - Prime Time

View as PDF

Submit solution

Points: 5
Time limit: 2.0s
Memory limit: 64M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
DWITE, January 2012, Problem 2

For your math homework this week, your teacher gave you five large numbers, and asked you to find their prime factors. However, these numbers aren't nearly large enough for someone with knowledge of programming like yourself. So, you decide to take the factorial of each of these numbers. Recall that N! (N factorial) is the product of the integers from 1 through N. It's your job now to create a program to help you do your homework.

The input will contain 5 test cases. Each test case contains a number N (2 \le N \le 10\,000).

The output will contain 5 lines of output, each representing the prime factorization of the given number, which should be of the form: p_1^{e_1} \times p_2^{e_2} \times \dots \times p_k^{e_k} where p_1, p_2, \dots, p_k are the distinct prime factors of the given number in increasing order, and e_1, e_2, \dots, e_k are their exponents.

Sample Input

2
3
5
10
20

Sample Output

2^1
2^1 * 3^1
2^3 * 3^1 * 5^1
2^8 * 3^4 * 5^2 * 7^1
2^18 * 3^8 * 5^4 * 7^2 * 11^1 * 13^1 * 17^1 * 19^1

Attribution-NonCommercial-ShareAlike 3.0 Unported (CC BY-NC-SA 3.0) Problem Resource: DWITE


Comments

There are no comments at the moment.