HackerRank Number Theory – Megaprime Numbers

Challenge: Megaprime Numbers

Subdomeniu: Number Theory (number-theory)

Scor cont: 50.0 / 50

Submission status: Accepted

Submission score: 1.0

Submission ID: 464744070

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/megaprime-numbers/problem

Cerinta

A [prime](https://en.wikipedia.org/wiki/Prime_number) number is an integer greater than $1$ that has no positive divisors other than $1$ and itself.

We call a number *megaprime* if it is prime and all of its individual digits are prime. For example, $53$ is megaprime because it is prime and all its digits ($5$ and $3$) are prime; however, $35$ is not megaprime because it is not prime (it's divisible by $5$ and $7$), and $13$ is not megaprime because it has a non-prime digit ($1$ is not prime).

Given two long integers, $first$ and $last$, find and print the total number of megaprime numbers in the inclusive range between $first$ and $last$.

Input Format

Two space-separated long integers describing the respective values of $first$ and $last$.

Output Format

Print a long integer denoting the total number of megaprimes in the inclusive interval between $first$ and $last$.

Constraints

* $1 \le first \le last \le 10^{15}$
* $last - first \le 10^{9}$

Cod sursa

#include <bits/stdc++.h>

inline bool hasPrimeDigitsOnly(long long n) {
    while (n > 0) {
        int d = int(n % 10);
        if (d != 2 && d != 3 && d != 5 && d != 7) {
            return false;
        }
        n /= 10;
    }
    return true;
}

std::vector<int> getPrimesTill(int max) {
    assert(max >= 1);
    std::vector<int> primes;
    std::vector<bool> isPrime(1 + max, true);
    isPrime[0] = false;
    isPrime[1] = false;
    for (int i = 2; i * i <= max; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j <= max; j += i) {
                isPrime[j] = false;
            }
        }
    }
    for (int i = 2; i < (int)isPrime.size(); i++) {
        if (isPrime[i]) {
            primes.push_back(i);
        }
    }
    return primes;
}

const int MAX_ROOT = (int)std::sqrt(1e15);

int countMegaPrimes(long long first, long long last) {
    assert(1 <= first && last <= (long long)MAX_ROOT * MAX_ROOT);
    if (first > last) {
        return 0;
    }
    static std::vector<int> primes = getPrimesTill(MAX_ROOT);
    std::vector<bool> isPrime(last - first + 1, true); // isPrime[i] <-> (i + first) is prime
    for (int p : primes) {
        long long p2 = 1LL * p * p;
        if (p2 > last) {
            break;
        }
        long long from = std::max(1LL * p, (first + p - 1) / p) * p;
        assert(from >= first);
        int fromShifted = (int)(from - first);
        int lastShifted = (int)(last - first);
        for (int i = fromShifted; i <= lastShifted; i += p) {
            isPrime[i] = false;
        }
    }
    int count = 0;
    for (int i = 0; i < (int)isPrime.size(); i++) {
        if (isPrime[i] && hasPrimeDigitsOnly(i + first)) {
            count++;
        }
    }
    return count;
}

int main() {
    long long first, last;
    scanf("%lld %lld", &first, &last);
    const int CHUNK = 10 * 1000 * 1000;
    const int CHUNK_FIRST = 2222222; // 7 digits
    const int CHUNK_LAST = 7777777; // 7 digits
    const int LAST_BEFORE_CHUNK = 777777; // 6 digits
    long long count = 0;
    if (last <= LAST_BEFORE_CHUNK) {
        count = countMegaPrimes(first, last);
    } else {
        assert(last > LAST_BEFORE_CHUNK);
        if (first <= LAST_BEFORE_CHUNK) {
            count = countMegaPrimes(first, LAST_BEFORE_CHUNK);
            first = LAST_BEFORE_CHUNK + 1;
        }
        assert(first <= last);
        for (long long partFirst = first / CHUNK * CHUNK + CHUNK_FIRST; partFirst <= last; partFirst += CHUNK) {
            if (hasPrimeDigitsOnly(partFirst)) {
                long long partLast = partFirst - CHUNK_FIRST + CHUNK_LAST;
                count += countMegaPrimes(std::max(first, partFirst), std::min(last, partLast));
            }
        }
    }
    printf("%lld", count);
    return 0;
}