#include <bits/stdc++.h>

using namespace std;

//**************************************************************************
// HackerRank Prepare > Mathematics > Fundamentals: Leonardo's Prime Factors
//**************************************************************************

string ltrim(const string &);
string rtrim(const string &);

// Brute force: For each integer from 1 to N, find the number of prime
// factors of each integer and then find the number of maximum unique
// prime factors.

// efficient approach: First Generate all prime numbers. Multiply
// consecutive prime numbers (starting from first prime number) one
// after another until the product is <= N. The idea is based on
// simple fact that the first set of prime numbers can cause maximum
// unique prime factors.

int primeCount(long n) {
    if (n == 1)
        return 0;
    
    vector<int32_t> primes = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};

    int count = 0;
    // uint64_t needed to accomodate the result of multiplied primes up to 53.
    uint64_t product = 1;
    for (size_t i = 0; i < primes.size(); i++)
    {
        product *= primes[i];
        if (product > (uint64_t)n)
            return count;
        count++;
    }
    
    return count;
}

int main()
{
    ofstream fout(getenv("OUTPUT_PATH"));

    // string q_temp;
    // getline(cin, q_temp);

    // int q = stoi(ltrim(rtrim(q_temp)));
    int q = 9;

    // test cases
    vector<long> v = {100,1,2,3,500,5000,10000000000,614889782588491410,614889782221484655};
    vector<long> results = {3,0,1,1,4,5,10,15,14};    

    cout << setw(20) <<   "n" << setw(8) << "result"    << setw(10) << "expected" << "\n";
    cout << setw(20) << "---" << setw(8) << "------"    << setw(10) << "--------" << "\n";
    
    for (int q_itr = 0; q_itr < q; q_itr++) {
        //string n_temp;
        //getline(cin, n_temp);
        
        //long n = stol(ltrim(rtrim(n_temp)));
        long n = v[q_itr];
        int result = primeCount(n);
        
        cout << setw(20) << n   << setw(8) << result   << setw(10) << results[q_itr] << "\n";
    }

    cout << endl;    
    cout << setw(21) << "Max N = 10^18:" << setw(21) << setprecision(0) << fixed << pow(10, 18) << endl;
    cout << setw(21) << "INT64_MAX:" << setw(21) << INT64_MAX << endl;    
    cout << setw(21) << "UINT64_MAX:" << setw(21) << UINT64_MAX << endl;

    ulong x = 1;
    vector<int32_t> primes = {2,3,5,7,11,13,17,19,21,29,31,37,41,43,47,53};
    for (auto i: primes)
        x *= i;
    cout << setw(21) << "product of primes:" << setw(21) << x << endl;
    
    fout.close();

    return 0;
}

std::function<int(int)> f_isspace = [](int x){ return isspace(x); };

string ltrim(const string &str) {
    string s(str);

    s.erase(
        s.begin(),
        find_if(s.begin(), s.end(), not_fn(f_isspace))
    );

    return s;
}

string rtrim(const string &str) {
    string s(str);

    s.erase(
        find_if(s.rbegin(), s.rend(), not_fn(f_isspace)).base(),
        s.end()
    );

    return s;
}