UT Martin Competitive Programming Guidebook

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== Kattis: Prime Sieve ======

===== C++ Source =====
<file python primesieve.cpp>
#include <bitset>
#include <cmath>
#include <vector>
#include <iostream>

using namespace std;
 
const int MAX_PRIMES=100000000;   // Note the problem bounds (up to 10^8)
//vector<int> primes;             // Note the restrictive memory limit: 50MB is probably too small for all the primes!
                                  // 4 bytes/int * 5761455 primes ~ 22 MB alone!

 
bitset<MAX_PRIMES> nums;          // true for each prime
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
  nums[0] = nums[1] = false;
  for(int i=2; i<=sqrt(n)+1; i++) // filter out non-primes
    if(nums[i])
      for(int j=i*i; j<n+2; j+=i)   
    nums[j] = false;
}  
 
int main() {
  int n, q, x, total=0;

  cin >> n >> q;                 // read initial values
  sieve(n);                      // calculate prime flags (only)

  for(int i=2; i<=n; i++)        // count primes in range
    if(nums[i])
      total++;
  
  cout << total << endl;         // print total number of primes

  for(int i=0; i<q; i++) {       // query, print results from flags
    cin >> x;
    if(nums[x])
      cout << "1" << endl;
    else
      cout << "0" << endl;
  }
  
  return 0;
}
</file>

===== Solution Explanation =====
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).

==== 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

Page Tools
