#ポラード・ローアルゴリズムによって素因数を発見する #参考元:https://judge.yosupo.jp/submission/6131 def Find_Factor_Rho(N): if N==1: return 1 from math import gcd m=1<<(N.bit_length()//8+1) for c in range(1,99): f=lambda x:(x*x+c)%N y,r,q,g=2,1,1,1 while g==1: x=y for i in range(r): y=f(y) k=0 while k1: if Miller_Rabin_Primality_Test(N): res.append([N,1]) N=1 else: j=Find_Factor_Rho(N) k=0 while N%j==0: N//=j k+=1 res.append([j,k]) if N>1: res.append([N,1]) res.sort(key=lambda x:x[0]) return res def integer_product(T): a=1 for t in T: a*=t return a from itertools import product def divisors(X): E=[[pow(p,k) for k in range(e+1)] for p,e in X] A=[integer_product(t) for t in product(*E)] A.sort() return A def check(N,r): p=N%r while N: if N%r!=p: return False N//=r return True #================================================ N=int(input()) Y=Pollard_Rho_Prime_Factorization(N) D=divisors(Y) X=N+1 for a in D: M=N//a Y=Pollard_Rho_Prime_Factorization(M-1) B=divisors(Y) for p in B: if p>=X: break if 2<=p and check(N,p): X=p print(X)