/* -*- coding: utf-8 -*- * * 407.cc: No.407 鴨等素数間隔列の数え上げ - yukicoder */ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; /* constant */ const int MAX_N = 1000000; const int MAX_L = 10000000; const int MAX_P = MAX_L / 2; typedef long long ll; /* typedef */ typedef vector vi; /* global variables */ bool primes[MAX_L / 2 + 1]; /* subroutines */ void gen_primes(int maxp, vi &pnums) { memset(primes, true, sizeof(primes)); primes[0] = primes[1] = false; int p; for (p = 2; p * p <= maxp; p++) if (primes[p]) { pnums.push_back(p); for (int q = p * p; q <= maxp; q += p) primes[q] = false; } for (; p <= maxp; p++) if (primes[p]) pnums.push_back(p); } /* main */ int main() { int n, l; cin >> n >> l; n--; vi pnums; int maxp = l / n; gen_primes(maxp, pnums); int pn = pnums.size(); //printf("pn=%d\n", pn); ll sum = 0; for (vi::iterator vit = pnums.begin(); vit != pnums.end(); vit++) { int &p = *vit; sum += l - n * p + 1; } printf("%lld\n", sum); return 0; }