#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<string>
#include<numeric>
#include<set>
#include<unordered_set>
#include<queue>
#include<bitset>
#include<list>

using namespace std;

long long u(std::string str)
{
    long long n = 0;
    for (auto x : str)
        n = n * 10 + (x - '0');
    return n;
}

int Hamming_number_part2(std::string N, int K)
{
    int r = 0;
    int q = 0;

    std::vector<bool> a(K + 1, true);
    for (size_t i = 2; i <= K; ++i)
        for (size_t j = 2 * i; j <= K; j += i)
            a[j] = false;

    std::vector<int> b;
    for (size_t i = 2; i <= K; ++i)
        if (a[i])
            b.push_back(i);

    std::list<long long> nums;
    nums.push_back(1);

    std::vector<decltype(nums.cbegin())> pos(b.size(), nums.cbegin());
    std::vector<long long> temp(b.size());

    auto n = u(N);
    while (nums.back() < n)
    {
        for (size_t i = 0; i < b.size(); ++i)
        {
            while ((*pos[i]) * b[i] <= nums.back())
                ++pos[i];
            temp[i] = (*pos[i]) * b[i];
        }

        auto f = *std::min_element(temp.cbegin(), temp.cend());
        nums.push_back(f);
        ++r;
    }

    return r;
}

int Hamming_number_part1(std::string N, int K)
{
    std::set<long long> s;
    int r = 0;
    int q = 0;

    std::vector<bool> a(K + 1, true);
    for (size_t i = 2; i <= K; ++i)
        for (size_t j = 2 * i; j <= K; j += i)
            a[j] = false;

    std::vector<int> b;
    for (size_t i = 2; i <= K; ++i)
        if (a[i])
            b.push_back(i);

    for (auto x : b)
        s.insert(x);

    auto n = u(N);
    while (!s.empty())
    {
        auto f = *s.begin();

        size_t i = 0;

        while (i < b.size() && f % b[i] != 0)
            ++i;

        while(i < b.size())
        {
            auto x = b[i];
            auto f1 = f*x;

            if (f1 <= n)
            {
                if (s.count(f1) > 0)
                    cout << f1 << endl;
                //cout << f*x << endl;
                s.insert(f1);
                ++q;
            }
            ++i;
        }
        s.erase(s.begin());
        ++r;
        //if (r % 10 == 0)
        //  cout << f << endl;
    }
    cout << q << endl;
    return r+1;
}

int main()
{
    long long t = 1e10;
    cout << t << endl;
    cout << Hamming_number_part2(to_string(t), 100) << endl;

    system("PAUSE");

    return 0;
}