Programming contests

DEIK Regionális Programozó Csapatverseny, egyetemi/főiskolai kategória, 2016. december 4.

December 4, 2016 10:10 AM – December 4, 2016 3:10 PM

Factors

The fundamental theorem of arithmetic states that every integer greater than 1 can be uniquely represented as a product of one or more primes. While unique, several arrangements of the prime factors may be possible. For example:

            10 = 2 * 5                20 = 2 * 2 * 5
               = 5 * 2                   = 2 * 5 * 2
                                         = 5 * 2 * 2

Let f(k) be the number of different arrangements of the prime factors of k. So f(10) = 2 and f(20) = 3.

Given a positive number n, there always exists at least one number k such that f(k) = n. We want to know the smallest such k.

Input Specification

The input consists of at most 1000 test cases, each on a separate line. Each test case is a positive integer n < 263.

Output Specification

For each test case, display its number n and, after a space, the smallest number k > 1 such that f(k) = n. The numbers in the input are chosen such that k < 263.

Sample Input

  1. 1
  2. 2
  3. 3
  4. 105
download as text file

Output for Sample Input

  1. 1 2
  2. 2 6
  3. 3 12
  4. 105 720
download as text file
University of Debrecen; Faculty of Informatics; v. 03/01/2019