75 lines
1.2 KiB
Java
75 lines
1.2 KiB
Java
package chelper;
|
|
|
|
import java.util.ArrayList;
|
|
import java.util.List;
|
|
|
|
import io.InputReader;
|
|
import io.OutputWriter;
|
|
import misc.SimpleSavingChelperSolution;
|
|
|
|
|
|
public class TaskA extends SimpleSavingChelperSolution {
|
|
|
|
public void solve(int testNumber, InputReader in, OutputWriter out) {
|
|
wrapSolve(testNumber, in, out);
|
|
}
|
|
|
|
List<Integer> primes(int n) {
|
|
boolean[] a = new boolean[n];
|
|
|
|
List<Integer> res = new ArrayList<>();
|
|
|
|
for (int i = 2; i < n; i++) {
|
|
if (a[i]) {
|
|
continue;
|
|
}
|
|
|
|
res.add(i);
|
|
|
|
for (int j = i; j < n; j += i) {
|
|
a[j] = true;
|
|
}
|
|
}
|
|
|
|
return res;
|
|
}
|
|
|
|
@Override
|
|
public void solve(int testNumber) {
|
|
int N = 1100000;
|
|
|
|
List<Integer> primes = primes(N);
|
|
|
|
int x2 = in.nextInt();
|
|
|
|
int r = x2 + 1;
|
|
int l = x2;
|
|
|
|
for (Integer prime : primes) {
|
|
if (x2 % prime == 0) {
|
|
l = x2 - prime + 1;
|
|
}
|
|
}
|
|
|
|
int minX0 = x2;
|
|
|
|
for (Integer prime : primes) {
|
|
int minX1 = (l + prime - 1) / prime * prime;
|
|
|
|
if (minX1 >= r) {
|
|
continue;
|
|
}
|
|
|
|
int next = minX1 - prime + 1;
|
|
if (minX1 == prime) {
|
|
next = prime;
|
|
}
|
|
|
|
minX0 = Math.min(minX0, next);
|
|
}
|
|
|
|
out.println(minX0);
|
|
|
|
}
|
|
}
|