Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cmath>
- #include <iostream>
- #include <map>
- #include <fstream>
- #include <vector>
- using namespace std;
- const int N = 10000000;
- int main()
- {
- int lp[N+1];
- vector< long long > pr;
- for (int i=2; i<=N; ++i)
- {
- if (lp[i] == 0)
- {
- lp[i] = i;
- pr.push_back (i);
- }
- for (int j=0; j<(int)pr.size() && pr[j]<=lp[i] && i*pr[j]<=N; ++j)
- lp[i * pr[j]] = pr[j];
- }
- long long n;
- long long ans=0;
- int p;
- cin >> n >> p;
- for (int i = 0; i < pr.size(); i++){
- bool f=true;
- long long cur=1;
- for (int j = 0; j < p-1; j++){
- if (cur*pr[i]<=n){
- cur*=pr[i];
- }
- else{
- f=false;
- break;
- }
- }
- if (f){
- ans++;
- }
- else{
- break;
- }
- }
- cout <<ans<<endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement