[EN] Prime numbers and speed
In an ICPC-style contest, 3-person teams compete in programming challenges, and they are allowed to bring a "notebook" into the contest. A notebook is a printable document, that teams usually fill with implementations of common algorithms, so that they are able to pull them out if needed in a contest. The other day, my ICPC team and I participated in one such contest (though an unofficial one) and we got stuck on a problem. Nevermind the details, but the solution called for finding all primes out of about a million numbers that were less than a trillion (that's 10 to the 12th power). Accordingly, our code looked something like this: // ... using ull = uint64_t; int main() { // ... vector<ull> numbers; populate(numbers); vector<ull> primes; for (ull x : numbers) if (is_prime(x)) primes.push_back(x); // ... } The only missing piece was fast primality testing. But since we already have that algorithm in o...