| Both sides previous revision
Previous revision
Next revision
|
Previous revision
|
files:cpp:primesieve [2018/08/10 09:21]
jguerin Added solution explanation. |
files:cpp:primesieve [2018/09/14 16:35] (current)
jguerin Moved the first sentence to the explanation header as a terse explanation. |
| vector<int> primes; // list of primes | vector<int> primes; // list of primes |
| | |
| | # Implemented from Wikipedia |
| void sieve(int n) { // eratosthenes as a drop-in solution | void sieve(int n) { // eratosthenes as a drop-in solution |
| nums.set(); // set all values to true | nums.set(); // set all values to true |
| int n, q, x, total=0; | int n, q, x, total=0; |
| |
| cin >> n >> q; // read initial values | cin >> n >> q; // read initial values |
| sieve(n); // calculate prime flags (only) | sieve(n); // calculate prime flags (only) |
| |
| for(int i=2; i<=n; i++) // count primes in range | for(int i=2; i<=n; i++) // count primes in range |
| if(nums[i]) | if(nums[i]) |
| total++; | total++; |
| | |
| cout << total << endl; // print value | cout << total << endl; // print total number of primes |
| |
| for(int i=0; i<q; i++) { // query, print results from flags | for(int i=0; i<q; i++) { // query, print results from flags |
| cin >> x; | cin >> x; |
| if(nums[x]) | if(nums[x]) |
| |
| ===== Solution Explanation ===== | ===== Solution Explanation ===== |
| | The title of the problem is a strong hint towards its intent to educate the reader about Prime Sieves. |
| | |
| ==== Potential "gotchas" ==== | ==== Potential "gotchas" ==== |
| The title of the problem is a strong hint towards its intent to educate the reader about Prime Sieves. Python3 can be immediately ruled out as a //likely// solution due to the problem bounds. Note that you need to compute 1 ≤ //n// ≤ 10<sup>8</sup> primes in the worst case (and that they will definitely test this upper bound!). | Python3 can be immediately ruled out as a //likely// solution due to the problem bounds. Note that you need to compute 1 ≤ //n// ≤ 10<sup>8</sup> primes in the worst case (and that they will definitely test this upper bound!).((Since we are not in a programming contest like the [[https://icpc.baylor.edu/|ACM ICPC]], we also have the benefit of hindsight--the [[https://open.kattis.com/problems/primesieve/statistics|problem statistics]] for the problem immediately identify that Python is a bad choice (constituting a very small minority of submissions, and then only in Python2.) )) |
| |
| The second thing thing that we can most likely rule out is the //storage// of each prime. Note that the problem doesn't require printing //primes themselves//, only //identifying primes//. Indeed, we could run our Sieve of Eratosthenes to see that there are 5761455 //primes// * 4 //bytes per prime// = 23045820 //bytes// required (or 21.978 MB) required for storage.((This test is plausible in a contest setting by simply running the prime sieve in C++ over the max bound of 10<sup>8</sup> and counting the resulting flags. Alternatively, if we know that the [[http://mathworld.wolfram.com/PrimeCountingFunction.html|prime counting function]] has a lower bound of π(10<sup>8</sup>) = 10<sup>8</sup>/ln 10<sup>8</sup> = 5428681 we could have come up with a faster (and close enough) approximation.)) Although the [[cpp:bitset|bitsets]] is more space efficient than a [[cpp:vector|vector]] of bools, we //only// have 50MB to work with. Since the [[cpp:vector|vector]] of primes is not key to the sieve, we simply eliminate it (which will also speed up our processing). | The second thing thing that we can most likely rule out is the //storage// of each prime. Note that the problem doesn't require printing //primes themselves//, only //identifying primes//. Indeed, we could run our Sieve of Eratosthenes to see that there are 5761455 //primes// * 4 //bytes per prime// = 23045820 //bytes// required (or 21.978 MB) required for storage.((This test is plausible in a contest setting by simply running the prime sieve in C++ over the max bound of 10<sup>8</sup> and counting the resulting flags. Alternatively, if we know that the [[http://mathworld.wolfram.com/PrimeCountingFunction.html|prime counting function]] has a lower bound of π(10<sup>8</sup>) = 10<sup>8</sup>/ln 10<sup>8</sup> = 5428681 we could have come up with a faster (and close enough) approximation.)) Although the [[cpp:bitset|bitsets]] is more space efficient than a [[cpp:vector|vector]] of bools, we //only// have 50MB to work with. Since the [[cpp:vector|vector]] of primes is not key to the sieve, we simply eliminate it (which will also speed up our processing). |
