ヒント: この問題の最後のサンプルは最大ケースです。
サンプルに最大ケースが入っている場合、そこから何らかの情報を読み取ったり最大ケースに対して正解できるかの判定が(提出前に)行えたりします。

この問題の場合、最大ケースの答えが \(2 \times 10^9\) 程度であることが分かります。ここから

• 全探索することはやや無謀である
• (例えば) 半分全列挙のような、効率的な探索ができたら実行時間制限に間に合いそうだ

という予想を得ます。ここでは半分全列挙を実現することを考えます。どのようにすればよいでしょうか ?

• 配列 \(U=(1),V=(1)\) を用意します。
• \(2\) 以上 \(P\) 以下の全ての素数 \(q\) について、以下を繰り返す。
  • \(U,V\) のうち小さい方を \(W\) とし、 \(W\) に次のような操作を施す。
    • \(W\) の各要素に \(q\) のべき乗を掛けたものであって、値が \(N\) 以下のものを全て \(W\) に追加する。
• 最後に、半分全列挙におけるマージの要領で \(U,V\) の各配列から \(1\) 要素ずつ選択して掛けた時に \(N\) 以下となるような組の数を数え上げる。

つまり、 \(P\) 以下の素因数を適切に \(2\) つの集合に分けた上で、各集合内の素因数しか持たない数を列挙し、最後にそれらをマージして和集合内の素因数しか持たない数を数え上げています。

この解法の計算量を机上で見積もるのは困難ですが、実際に実装して最大ケースを試すと \(|U|,|V| \le 5 \times 10^6\) 程度で済むことがわかり、これらをソートして半分全列挙におけるマージをしても十分高速なことが分かります。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

void step(vector<long long> &a,long long p,long long mxm){
  long long sz=a.size();
  for(long long i=0;i<sz;i++){
    long long ad=a[i];
    while(1){
      ad*=p;
      if(ad>mxm){break;}
      a.push_back(ad);
    }
  }
}

int main(){
  vector<long long> pl={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};
  long long n,p;
  cin >> n >> p;
  while(p<pl.back()){pl.pop_back();}

  vector<long long> u={1},v={1};
  for(auto &nx : pl){
    if(u.size()<v.size()){step(u,nx,n);}
    else{step(v,nx,n);}
  }
  // cerr << u.size() << " " << v.size() << "\n";

  sort(u.begin(),u.end());
  sort(v.begin(),v.end());
  long long res=0,j=v.size()-1;
  for(long long i=0;i<u.size();i++){
    long long mv=(n/u[i]);
    while(j>=0 && mv<v[j]){j--;}
    if(j<0){break;}
    res+=(j+1);
  }
  cout << res << "\n";
  return 0;
}