Differences
This shows you the differences between two versions of the page.
| Both sides previous revision
Previous revision
|
|
files:cpp:primesieve [2018/09/14 16:30]
jguerin |
files:cpp:primesieve [2018/09/14 16:35] (current)
jguerin Moved the first sentence to the explanation header as a terse explanation. |
| |
| ===== 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!).((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.) )) | 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). |
