// verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/1276
#include "src/math/sieve_of_eratosthenes.hpp"
#include <iostream>
using namespace std;
int main() {
SieveOfEratosthenes sieve(1299709);
int n;
while (cin >> n, n) {
int lcnt = 0, rcnt = 0;
while (!sieve.is_prime(n - lcnt)) ++lcnt;
while (!sieve.is_prime(n + rcnt)) ++rcnt;
cout << lcnt + rcnt << endl;
}
return 0;
}
#line 1 "test/math/sieve_of_eratosthenes/aoj_1276.test.cpp"
// verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/1276
#line 1 "src/math/sieve_of_eratosthenes.hpp"
#include <numeric>
#include <utility>
#include <vector>
class SieveOfEratosthenes {
private:
std::vector<int> min_factor;
public:
SieveOfEratosthenes(int n) : min_factor(n + 1) {
std::iota(min_factor.begin(), min_factor.end(), 0);
for (int p = 2; p * p <= n; ++p) {
if (min_factor[p] < p) continue;
for (int q = p * p; q <= n; q += p) {
if (min_factor[q] == q) min_factor[q] = p;
}
}
}
bool is_prime(int n) { return n > 1 && min_factor[n] == n; }
std::vector<std::pair<int, int>> factorize(int n) {
std::vector<std::pair<int, int>> res;
while (n > 1) {
int p = min_factor[n];
int exp = 0;
while (min_factor[n] == p) {
n /= p;
++exp;
}
res.emplace_back(p, exp);
}
return res;
}
std::vector<int> divisor(int n) {
std::vector<int> res{1};
for (auto const &[p, exp] : factorize(n)) {
int sz = res.size();
for (int i = 0; i < sz; ++i) {
int x = 1;
for (int j = 0; j < exp; ++j) {
x *= p;
res.push_back(res[i] * x);
}
}
}
return res;
}
};
#line 4 "test/math/sieve_of_eratosthenes/aoj_1276.test.cpp"
#include <iostream>
using namespace std;
int main() {
SieveOfEratosthenes sieve(1299709);
int n;
while (cin >> n, n) {
int lcnt = 0, rcnt = 0;
while (!sieve.is_prime(n - lcnt)) ++lcnt;
while (!sieve.is_prime(n + rcnt)) ++rcnt;
cout << lcnt + rcnt << endl;
}
return 0;
}
test/math/sieve_of_eratosthenes/aoj_1276.test.cpp