/* -*- coding: utf-8 -*- * * 106.cc: No.106 素数が嫌い!2 - 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 = 2000000; /* typedef */ /* global variables */ bool primes[MAX_N + 1]; int pcnts[MAX_N + 1]; /* subroutines */ void gen_primes(int maxp) { memset(primes, true, sizeof(primes)); primes[0] = primes[1] = false; int p; for (p = 2; p * p <= maxp; p++) if (primes[p]) { pcnts[p]++; for (int q = p * 2; q <= maxp; q += p) primes[q] = false, pcnts[q]++; } for (; p <= maxp; p++) if (primes[p]) pcnts[p]++; } /* main */ int main() { int n, k; cin >> n >> k; gen_primes(n); int cnt = 0; for (int i = 2; i <= n; i++) if (pcnts[i] >= k) cnt++; printf("%d\n", cnt); return 0; }