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.
Do you submit only answers or do you execute code in an online judge? If it's answers only then you can parallelize sieve of Eratosthenes with CUDA to find primes, it should take ~10 seconds for 10^12 numbers on a relatively modern GPU.
Code is submitted — much in the same manner as codeforces, just in more buggy and clumsy interface and executing system :)
Have you heard of segmented sieve? Perhaps a similar strategy would work here (can you provide time limit?). After you find primes up to sqrt(1e11) you create a boolean array of size 1e8 representing the possible suffixes after the prefix. Then, for each prime you found, cross off the suffixes that are eliminated by that prime
Actually, you need to find primes up to sqrt(1e12) and a boolean array of size 1e7 but other than that this is the correct approach.
Ah I see you're right about the 1e7 part, my mistake. That would cover all 7-digit suffixes.
But then, wouldn't 1e11 be sufficient to cover all 11-digit numbers?
Right, that was my mistake — 1e11 is indeed sufficient.
What we essentially have to do in the problem is to determine how many prime numbers are in the range [BASE * 10^7, (BASE + 1) * 10^7) where BASE is a 4-digit number given as an input. There's special handling needed for the case when BASE = 0 but other than that we need to run primality check for 11-digit numbers.
If the number consists of at most 11 digits, it means that it's less than 10^11.
If the number is less than 10^11 (let's say, it's N < 10^11), then only one of the following two statements is true: 1) N is prime itself; 2) N = A * B where 1 < min(A, B) < sqrt(10^11) < 320000.
Second statement is easy to prove by contradiction — if it's not true, then there exist some A >= sqrt(10^11) and B >= sqrt(10^11), then N = A * B >= sqrt(10^11) * sqrt(10^11) = 10^11 but it contradicts with the problem statement (N < 10^11).
So in order to check if the number is prime we just need to make sure that it doesn't have any divisor less than sqrt(10^11) < 320000.
Then we write a little modified Eratosthenes sieve: 1) initially we consider every number in the range [BASE * 10^7, (BASE + 1) * 10^7) to be prime; 2) then on each step we will tick off the numbers that are not prime similarly to how it's done for a normal sieve; more specifically, for every number X in the range [2, 320000) we can say that numbers of the form X * Y, where Y >= 1, BASE * 10 ^ 7 <= X * Y < (BASE + 1) * 10 ^ 7 are not prime.
There’re some small optimizations such as: 1) check only prime numbers in the range [2, 320000); 2) when ticking off numbers in the range [BASE * 10 ^ 7, (BASE + 1) * 10 ^ 7] start with and odd number an increment not by X but by 2X - but I think they’re not strictly needed to fit into the TL.
Here’s my code if it’s helpful — http://pastie.org/p/6ZKbNcMv9r8NHeSZmltA71
Hi and glad to see you! Thanks for careful explanations! It'll take some time for me to ingest them, but it looks impressive :)
By the way, there's a Telegram chat where you can ask questions about problems or anything else related to the contest — https://t.me/+kr0zuY3UJVJmOGRi?roistat_visit=1841079
Also, you're saying — "Out of 5 problems this is the only one I do not know how to approach.". How did you approach the last problem about aeroscooters? It's not trivial to write an optimal solution that fits into time limit.
Oh, sorry for misleading, I didn't solve it. I only did two simplest (1 and 4) and spent most of time on the 2nd. I thought I understand where to go with 2nd and 5th — particularly, I hoped to run slightly modified Dijkstra over "base" tree which on every step adds (virtual) edges for aeroscooters. It seemed there may be some "mega-test" which will require clever optimization based on the fact that aeroscooter edges from the given node all have equal cost (?) — but I regretfully lacked any motivation and time to try :(