Submission #45557094

---

Source Code Expand

#include <bits/stdc++.h>

namespace {
    using Num = long long int;
}

void find_primes(std::vector<Num>& primes, std::vector<bool>& not_primes, Num upper) {
    for(Num p{2}; (p*p)<=upper; ++p) {
        if (not_primes.at(p)) {
            continue;
        }
        for(Num i=p*2; i<=upper; i+=p) {
            not_primes.at(i) = true;
        }
    }

    for(Num p{2}; p<=upper; ++p) {
        if (!not_primes.at(p)) {
            primes.push_back(p);
        }
    }
}

void solve(std::istream& is, std::ostream& os) {
    using Num = long long int;
    Num n {0};
    is >> n;

    constexpr Num upper = 1000100LL;
    std::vector<Num> primes;
    std::vector<bool> not_primes(upper + 1, false);
    find_primes(primes, not_primes, upper);

    Num answer {0};
    Num a_index {0};
    for(;;) {
        const Num a = primes.at(a_index);
        if ((a * a * a * a * a) > n) {
            break;
        }

        Num b_index = a_index + 1;
        for(;;) {
            const Num b = primes.at(b_index);
            if ((a * a * b * b * b) > n) {
                break;
            }

            const Num c_index = b_index + 1;
            const Num lower = primes.at(c_index);
            if ((a * a * b * lower * lower) > n) {
                break;
            }

            Num c_upper = 288675;
            while((a * a * b * c_upper * c_upper) > n) {
                --c_upper;
            }

            auto it = std::upper_bound(primes.begin(), primes.end(), c_upper);
            const auto d = std::max(0LL, (it - primes.begin()) - c_index);
            answer += d;

            if (d == 0) {
                break;
            }
            ++b_index;
        }
        ++a_index;
    }

    os << answer << "\n";
    return;
}

int main(void) {
    solve(std::cin, std::cout);
    return 0;
}

Submission Info

Judge Result