Hi Friends! This problem is one of five in recently closed "semifinal" round of local contest held by MTS mobile operator (true tech champ 2024 or something like this). Out of 5 problems this is the only one I do not know how to approach. Round is over so it should be ok to discuss.
Mobile network operator sells "beautiful" phone numbers. They consist of 11
digits — first four are regional prefix, while other seven could be arbitrarily chosen by customer — the whole eleven-digit number should be prime (to be considered beautiful).
Input data give 4
-digit prefix — and output should give the total amount of beautiful (i.e. prime) numbers with such prefix. Example: 8916
yields 396749
.
I initially very silly tried to build array of primes up to about sqrt(1e11) = 330000
and then iterate over 5 mln
candidate odd numbers, testing with that prime array as divisors.
This is too slow — and no wonder. There could be over 300000
primes in the range and each of them will require trying every of 300000+
divisors :) I tried to use probable prime function from standard library, but it is still slow.
Precalc on 10000
prefixes seemed feasible but I didn't care to try (and anyway precalc time would be significant given 5 hours on all problems).
P.S. contest was notable for some issues so there is no guarantee the problem is not buggy/malformed.