No.1498 Factorization from -1 to 1
タグ : / 解いたユーザー数 30
作問者 :
sgsw
Problem Statement
Recently, Sonuke studied the sieve of Eratosthenes.
As a result, Sonuke became able to quickly compute the prime factorization of the sequence of natural numbers $S_i = i (1 \le i \le 100000)$.
However, that alone is not very interesting, so Sonuke decided to try prime factorization on some slightly unusual integer sequences as well.
First, Sonuke considered the prime factorization of $A_i = i^2 ( 1 \le i \le 100000)$. Sonuke immediately came up with a good idea.
Next, Sonuke considered the prime factorization of $B_i = i^2-1 ( 1 \le i \le 100000)$. Sonuke was able to solve this one right away too.
Finally, Sonuke considered the prime factorization of $X_i = i^2+1 ( 1 \le i \le$ 100000$100001)$, but
Sonuke noticed that the general term $X_i$ of this sequence, unlike the previous two, is not in a form that factors neatly.
As things stand, Sonuke cannot factorize $X_i$ when its value becomes very large, and is at a loss as to how to compute the prime factorization.
Please compute the prime factorization of $X_i(1 \le i \le$ 100000$100001)$ on Sonuke's behalf.
Input
$Q$ $q_1$ $q_2$ . . . $q_Q$
First, the total number of inputs $Q$ is given.
Here, $Q$ is a natural number satisfying $1 \le Q \le 100000$.
Then, over the following $i(1 \le i \le Q)$ lines, natural numbers $q_i(1 \le q_i \le $100000 $100001)$ are given.
There was an error in the constraints, so a correction has been made using strikethrough. We apologize.
Output
Output $Q$ lines.
On the $i(1 \le i \le Q)$-th line, output the result of the prime factorization of $X_{q_i}$.
Here, for the prime factorization of each term, output the prime factors of that number, including duplicates, in ascending order.
For the input and output, also refer to the examples below.
Also, print a newline at the end.
Sample
Sample 1
Input
8 3 1 4 1 5 9 2 6
Output
2 5 2 17 2 2 13 2 41 5 37
$X_3$ = $3^2 + 1 = 10 = 2 * 5 $.
$X_1$ = $1^2 + 1 = 2 $.
$X_4$ = $4^2 + 1 = 17 $.
$X_1$ = $1^2 + 1 = 2 $.
$X_5$ = $5^2 + 1 = 26 = 2 * 13 $.
$X_9$ = $9^2 + 1 = 82 = 2 * 41 $.
$X_2$ = $2^2 + 1 = 5 $.
$X_6$ = $6^2 + 1 = 37 $.
Sample 2
Input
5 8523 6189 6365 1311 37
Output
2 5 13 558781 2 29 660409 2 13 1558201 2 859361 2 5 137
Note that for the prime factorization of each term, the prime factors of that number must be output in ascending order.
Sample 3
Input
20 40887 72874 61303 51575 67282 63799 77986 73719 58829 55758 29693 85015 65766 31202 47690 25980 91221 41077 83153 79062
Output
2 5 181 923617 5310619877 2 5 13 37 781301 2 2437 545749 5 5 17 1601 6653 2 13 156550477 53 114751249 2 1321 2056961 2 29 29 269 7649 5 621790913 2 5 5 5 41 86017 2 13 4801 57901 51637 83761 5 194712961 3457 657893 17 37 1073069 2 11909 349369 2 5 461 366013 2 5 13 113 470689 5 1250159969
It seems there are terms whose only factor is a huge prime, such as $5310619877$. This may be difficult for Sonuke.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。