東京大学 情報理工学系研究科 創造情報学専攻 2007年8月実施 筆記試験 第1問

标签：

• Tokyo-University
• Divisor-Counting-Function
• Prime-Factorization
• Backtracking

Author

itsuitsuki

Description

Let $N$ be the number of divisors of a positive integer $J$. Let us compute the smallest $J$ for a given $N$. Note that $J$ and $1$ are included among the divisors of $J$.

(1) Calculate the smallest $J$ each for $N=5$ and $N=8$.

(2) Let $J$ be prime factorized as $J=\prod_{i=0}^{k-1}p_i^{a_i}$ where $p_i$s are mutually different prime numbers and $a_i$s are positive integers for $0\le i<k$. Describe $N$ in a mathematical formula.

(3) When $N$ is odd, what kind of number is $J$?

(4) Based on (2), describe the outline of a method to compute the smallest $J$ given $N$. Moreover, describe ways to decrease computational complexity.

(5) Calculate the smallest $J$ for $N=24$.