import java.util.Scanner;
public class Main {
private static int maxN = 5201314;
private static boolean[] primes = new boolean[maxN];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
setPrime();
for (int i = 2; i < n; i++) {
if (quickPow(i, n - 1, n) == 1) {
if (isPrimeRoot(i, n - 1)) {
System.out.println(i);
return;
}
}
}
System.out.println(-1);
sc.close();
}
private static boolean isPrimeRoot(int g, int P) {
for (int i = 2; i < P; i++) {
if (!primes[i] && quickPow(P, 1, i) == 0)
if (quickPow(g, P / i, P + 1) == 1)
return false;
while (P % i == 0) P /= i;
}
return true;
}
private static void setPrime() {
for (int i = 2; i < maxN; i++)
if (!primes[i])
for (int j = i * 2; j < maxN; j += i)
primes[j] = true;
}
private static int quickPow(int a, int b, int mod) {
int ans = 1;
for (; b != 0; b /= 2) {
if (b % 2 == 1) ans = (ans * a) % mod;
a = (a * a) % mod;
}
return ans;
}
}
第二题用dfs做的ac了但是是不是就只有一个用例...其实感觉自己写的有点问题～