#include using namespace std; #ifdef _WIN32 #define scanfll(x) scanf("%I64d", x) #define printfll(x) printf("%I64d", x) #else #define scanfll(x) scanf("%lld", x) #define printfll(x) printf("%lld", x) #endif #define rep(i,n) for(long long i = 0; i < (long long)(n); i++) #define repi(i,a,b) for(long long i = (long long)(a); i < (long long)(b); i++) #define pb push_back #define all(x) (x).begin(), (x).end() #define fi first #define se second #define mt make_tuple #define mp make_pair template bool chmin(T1 &a, T2 b) { return b < a && (a = b, true); } template bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); } using ll = long long; using ld = long double; using vll = vector; using vvll = vector; using vld = vector; using vi = vector; using vvi = vector; vll conv(vi& v) { vll r(v.size()); rep(i, v.size()) r[i] = v[i]; return r; } using P = pair; template ostream &operator<<(ostream &o, const pair &v) { o << "(" << v.first << ", " << v.second << ")"; return o; } template struct seq{}; template struct gen_seq : gen_seq{}; template struct gen_seq<0, Is...> : seq{}; template void print_tuple(basic_ostream& os, Tuple const& t, seq){ using s = int[]; (void)s{0, (void(os << (Is == 0? "" : ", ") << get(t)), 0)...}; } template auto operator<<(basic_ostream& os, tuple const& t) -> basic_ostream& { os << "("; print_tuple(os, t, gen_seq()); return os << ")"; } ostream &operator<<(ostream &o, const vvll &v) { rep(i, v.size()) { rep(j, v[i].size()) o << v[i][j] << " "; cout << endl; } return o; } template ostream &operator<<(ostream &o, const vector &v) { o << '['; rep(i, v.size()) o << v[i] << (i != v.size()-1 ? ", " : ""); o << "]"; return o; } template ostream &operator<<(ostream &o, const set &m) { o << '['; for (auto it = m.begin(); it != m.end(); it++) o << *it << (next(it) != m.end() ? ", " : ""); o << "]"; return o; } template ostream &operator<<(ostream &o, const map &m) { o << '['; for (auto it = m.begin(); it != m.end(); it++) o << *it << (next(it) != m.end() ? ", " : ""); o << "]"; return o; } template ostream &operator<<(ostream &o, const unordered_map &m) { o << '['; for (auto it = m.begin(); it != m.end(); it++) o << *it; o << "]"; return o; } void printbits(ll mask, ll n) { rep(i, n) { cout << !!(mask & (1ll << i)); } cout << endl; } #define ldout fixed << setprecision(40) static const double EPS = 1e-14; static const long long INF = 1e18; static const long long mo = 1e9+7; /**********************************************************/ // 前処理ありの素数判定 // 素数の最大値Mに対して先にconstructPrimesList(M)が必須! /**********************************************************/ // O(n log n) void sieve_of_eratosthenes(vector& primes, ll n) { primes.resize(n); for (ll i = 2; i < n; ++i) primes[i] = i; for (ll i = 2; i*i < n; ++i) if (primes[i]) for (ll j = i*i; j < n; j+=i) primes[j] = 0; } void getPrimesList(ll n, vector& primes_list) { vector tmpList; primes_list.clear(); primes_list.resize(0); primes_list.reserve(n / 5); sieve_of_eratosthenes(tmpList, n); rep(i, n) { if (tmpList[i]) primes_list.push_back(i); } } // 素数テーブル構築: O(n log n) vector primesList; // 素数リスト(primesListMaxまで)。こいつ自体を使うことあるかも。 set primesSet; ll primesListMax; void constructPrimesList(ll n) { if (primesListMax >= n) return; primesListMax = n; getPrimesList(n, primesList); for (ll i = 0; i < primesList.size(); i++) { primesSet.insert(primesList[i]); } } // constructされていないなら、O(n log n) // constructされているなら、O(log n) bool isPrimeLookup(ll n) { return primesSet.count(n); } // constructされていないなら、O(sqrt(n) log n) // constructされているなら、O(log n) // Divisor系は、最大nをMAXNとしてconstructPrimesList(sqrt(MAXN))で早くなる void getPrimeFactorizationList(ll n, vector& divisors_list) { divisors_list.clear(); divisors_list.resize(0); if (n <= 1) return; ll prime = 2; while (n >= prime * prime) { if (n % prime == 0) { divisors_list.push_back(prime); n /= prime; } else { prime++; } } divisors_list.push_back(n); } // constructされていないなら、O(sqrt(n) log n) // constructされているなら、O(log n) // Divisor系は、最大nをMAXNとしてconstructPrimesList(sqrt(MAXN))で早くなる void getDivisorsList(ll n, vector& divisors_list) { divisors_list.clear(); divisors_list.resize(0); vector fac_list; getPrimeFactorizationList(n, fac_list); map counter; for (auto x : fac_list) counter[x]++; divisors_list.push_back(1); for (auto x : counter) { ll tmp_size = divisors_list.size(); ll p = 1; for (ll i = 0; i < x.second; i++) { p *= x.first; for (ll j = 0; j < tmp_size; j++) divisors_list.push_back(divisors_list[j] * p); } } sort(divisors_list.begin(), divisors_list.end()); } // constructされていないなら、O(sqrt(n) log n) // constructされているなら、O(log n) ll getDivisorsNum(ll n) { vector divisors_list; getPrimeFactorizationList(n, divisors_list); map num; for (ll i = 0; i < divisors_list.size(); i++) { num[divisors_list[i]]++; } ll p = 1; for (auto x : num) { p *= x.second + 1; } return p; } /**********************************************************/ // 前処理なしの素数判定 /**********************************************************/ // Millar-Rabin Test using ull = unsigned long long; bool isPrimeSmall(const ll &n){ if(n == 2) return true; if(n < 2 || n%2 == 0) return false; const ll m = n-1, d = m / (m & -m); auto modpow = [&](ll a, ll b){ ll res = 1; while(b){ if(b&1) res = res*a%n; a = a*a%n; b >>= 1; } return res; }; auto suspect = [&](ll a, ll t){ a = modpow(a,t); while(t != -1+n && a != 1 && a != -1+n){ a = a*a%n; t *= 2; } return a == n-1 || t%2 == 1; }; static const ll witness[] = {2,7,61,0}; // n <= 2^32 for(const ll *w = witness; *w < n && *w; w++){ if(!suspect(*w,d)) return false; } return true; } bool isPrimeLarge(const ll &n){ if(n == 2) return true; if(n < 2 || n%2 == 0) return false; const ll m = n-1, d = m / (m & -m); auto modmul = [&](ll a, ll b){ ll res = 0; while(b){ if(b&1) res = ((ull)res+a)%n; a = ((ull)a+a)%n; b >>= 1; } return res; }; auto modpow = [&](ll a, ll b){ ll res = 1; while(b){ if(b&1) res = modmul(res,a); a = modmul(a,a); b >>= 1; } return res; }; auto suspect = [&](ll a, ll t){ a = modpow(a,t); while(t != -1+n && a != 1 && a != -1+n){ a = modmul(a,a); t *= 2; } return a == n-1 || t%2 == 1; }; static const ll witness[] = {2,325,9375,28178,450775,9780504,1795265022,0}; // n <= 2^64 for(const ll *w = witness; *w < n && *w; w++){ if(!suspect(*w,d)) return false; } return true; } bool isPrime(const ll &n){ return n < INT_MAX ? isPrimeSmall(n) : isPrimeLarge(n); } // ガウス素数=複素数の素数判定 bool isGaussianPrime(ll a, ll b) { if (a < 0) a = -a; if (b < 0) b = -b; if (a == 0) return b % 4 == 3 && isPrime(b); if (b == 0) return a % 4 == 3 && isPrime(a); return isPrime(a*a+b*b); } // 区間篩 // O( n log n ). const ll N = 100000000; // MAXPRIME const ll M = 10000; // SQRT(N) const ll K = 6000000; // NUMBER OF PRIMES, CHOOSE 9/8 * N / LOG(N) vector iterativeSieve() { static ll p[K], table[M]; for (ll i = 2; i < M; ++i) p[i] = i; for (ll i = 2; i*i < M; ++i) if (p[i]) for (ll j = i*i; j < M; j += i) p[j] = 0; p[0] = p[1] = 0; ll num = remove(p, p+M, 0) - p; for (ll m = M; m < N; m += M) { for (ll x = m; x < m+M; ++x) table[x-m] = x; for (ll i = 0, j; p[i]*p[i] < m+M; ++i) { if (p[i] >= m) j = p[i] * p[i]; else if (m % p[i] == 0) j = m; else j = m - (m % p[i]) + p[i]; for (; j < m+M; j += p[i]) table[j-m] = 0; } num = remove_copy(table, table+M, p+num, 0) - p; } return vector(p, p+num); } int main(void) { cin.tie(0); ios::sync_with_stdio(false); ll n, l; cin >> n >> l; constructPrimesList(l); ll ret = 0; for (auto p : primesList) { ll tmp = p * (n - 1); if (tmp <= l) ret += l - tmp + 1; } cout << ret << endl; return 0; }