Hide

Problem B
Pollard's p-1 Algorithm

Languages en is

Use Pollard’s $p-1$ algorithm to find a non-trivial factor of an integer $n$, using the random number $a=2$ and a boundary $B$. Given a boundary $B$, the problem expects it to be an inclused boundary, i.e., $a^{B!}$ should be computed before we decide no solution is found.

Input

First line consist of an integer $2 \leq n \leq 2^{63}-1$. The second line consist of an integer $1 \leq B \leq 10^5$, the boundary.

Output

Output any non-trivial factor of $n$ or $-1$ if none is found.

Sample Input 1 Sample Output 1
144948923
10
7
Sample Input 2 Sample Output 2
675103487
50000
-1

Please log in to submit a solution to this problem

Log in