Soluție HackerRank pentru Megaprime Numbers, subdomeniul Number Theory, în C++14. Include cerința formatată, exemple, explicația pașilor și cod sursă.
- Problemă: Megaprime Numbers
- Domeniu: Number Theory
- Limbaj: C++14
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
Cerință
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 ≤ first ≤ last ≤ 10^15
* last - first ≤ 10^9
Cod sursă
#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;
}