Submission #60537873

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/* -------------------------------------- HEADER FILES ---------------------------------------- */
/**
 *    username:  aditya_0670
 *    created: 2024-12-07 18:42:56
 **/
  #include <bits/stdc++.h>
  using namespace std;
/* ------------------------------------ MACROS & CONSTANTS ------------------------------------ */
  #ifndef ONLINE_JUDGE
      #include "debug.h"
  #else
      #define debug(...) ;
  #endif
  #define int             long long
  #define all(v)          (v).begin(), (v).end()
  #define rall(v)         (v).rbegin(), (v).rend()
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

/* -------------------------------------- HEADER FILES ---------------------------------------- */

/**
 *    username:  aditya_0670
 *    created: 2024-12-07 18:42:56
 **/

  #include <bits/stdc++.h>
  using namespace std;

/* ------------------------------------ MACROS & CONSTANTS ------------------------------------ */

  #ifndef ONLINE_JUDGE
      #include "debug.h"
  #else
      #define debug(...) ;
  #endif

  #define int             long long
  #define all(v)          (v).begin(), (v).end()
  #define rall(v)         (v).rbegin(), (v).rend()
  #define fastio          ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr)

  constexpr int MOD = 1E9 + 7;
  constexpr int INF = 1E18;


/* ------------------------------------ OTHER FUNCTIONS ------------------------------------ */


/* ------------------------------------ LAMBDA TEMPLATE ------------------------------------- */

  auto solve = [] -> void
  {
      int N; cin >> N;

      int limit = sqrt(N);
      
      vector<int> primes;

      auto seive =[&]() 
      {
          vector<bool> is_prime(limit + 1, true);
          is_prime[0] = is_prime[1] = false;

          for (int i = 2; i <= limit; ++i) 
          {
              if (is_prime[i]) 
              {
                  primes.push_back(i);
                  for (int j = 2 * i; j <= limit; j += i) 
                      is_prime[j] = false;
              }
          }
          return primes;
      };
      seive();

      auto f1 =[&]() 
      {
          int count = 0;
          for (int p : primes) 
          {
              int val = 1;
              for (int i = 0; i < 8; ++i) 
              {
                  if (val > N / p) {count--; break; }
                  val *= p;
              }
              if (val <= N) count++;
          }


          int sz = primes.size();
          for (int i = 0; i < sz; ++i) 
          {
              int p1_sq = (int)primes[i] * primes[i];
              if (p1_sq > N) break;

              for (int j = i + 1; j < sz; ++j) 
              {
                  int p2_sq = (int)primes[j] * primes[j];
                  if (p1_sq > N / p2_sq) break;

                  int product = p1_sq * p2_sq;
                  if (product <= N) count++;
              }
          }
          return count;
      };

      cout << f1() << '\n';
  };

/* ------------------------------------ MAIN FUNCTION --------------------------------------- */

  signed main() 
  {
      fastio;

      int t = 1;
      while (t--) solve();

      return 0;
  }

Submission Info

Judge Result