#include #include #include #include using namespace std; #define FOR(i, N) for(int i=0; i<(N); i++) #define REP(i, N) for(int i=1; i<=(N); i++) typedef pair Edge; struct Union_Find { vector parent, rank; Union_Find(int n){ parent.resize(n, 0); rank.resize(n, 0); for (int i=0; i rank[y]){ parent[y] = x; }else{ parent[x] = y; if (rank[x] == rank[y]){ rank[y]++; } } return; } }; int main() { int L, R; vector> edges; cin >> L >> R; for(int i=L; i<=R; i++){ if (i < R) edges.push_back({1, {i, i+1}}); for(int j=1; j<=sqrt(i); j++){ if (i % j == 0){ if (L <= j && j < i){ edges.push_back({0, {i, j}}); } if (L <= (i/j) && (i/j) < i && j != (i/j)){ edges.push_back({0, {i, i/j}}); } } } } sort(edges.begin(), edges.end()); int V = R - L + 1; int v_cnt = 0; int answer = 0; Union_Find uf(V); for (auto e : edges){ int cost = e.first; int e1 = e.second.first - L; int e2 = e.second.second - L; if (uf.get_parent(e1) != uf.get_parent(e2)){ uf.unite(e1, e2); answer += cost; v_cnt++; } if (v_cnt == V-1){ break; } } cout << answer << endl;; return 0; }