Differences

This shows you the differences between two versions of the page.

--- files:cpp:primesieve [2018/08/10 09:09]
jguerin Crated, added Kattis source, explanation.
+++ files:cpp:primesieve [2018/09/14 16:35] (current)
jguerin Moved the first sentence to the explanation header as a terse explanation.
@@ Line 18: / Line 18: @@
 vector<int> primes;               // list of primes
+# Implemented from Wikipedia
 void sieve(int n) {               // eratosthenes as a drop-in solution
   nums.set();                     // set all values to true
@@ Line 31: / Line 31: @@
   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])
       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;
     if(nums[x])
@@ Line 53: / Line 53: @@
 ===== Solution Explanation =====
-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!).
+The title of the problem is a strong hint towards its intent to educate the reader about Prime Sieves.
+==== Potential "gotchas" ====
+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//.
+==== Finding the Solution ====
+Once we understand the bounds of the problem, processing the needed values is mostly done by parsing the [[cpp:bitset|bitset]] that results from the sieve, either to count the primes in our range or to query the primality of inputs in a loop.

UT Martin Competitive Programming Guidebook

User Tools

Site Tools

Differences

Page Tools