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.
====== Prime Number Generator: Sieve of Eratosthenes  ======

Prime sieves((A sieve (Pronounced like "give" not "sleeve".) is a physical metaphor (i.e., a mesh bowl in a kitchen) for an algorithmic technique used in number theory to "sift out" a class of numbers in a given set or range.)) are common devices for generating prime numbers in a given range. These lists can be used for quick verification of relatively small prime numbers (typically no larger than 10<sup>8</sup>) when many such verifications may be necessary.


===== Source =====
<file python sieve.py>
from math import *

def sieve(n):
    primes = [True] * (n+1)                             # true for each primes
    primes[0] = primes[1] = False
    for i in range(2, int(sqrt(n))+1):                  # filter out non-primes
        if primes[i]:
            for j in range(i**2, n+1, i):
                primes[j] = False
    return [i for i in range(len(primes)) if primes[i]] # generate primes from True values
 
primes = sieve(1000000)
</file>

<file c++ sieve.cpp>
#include <bitset>
#include <cmath>
#include <vector>

using namespace std;
 
const int MAX_PRIMES=100000000;

bitset<MAX_PRIMES+1> nums;        // true for each prime
vector<int> primes;               // list of primes

void sieve(int n) {
  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;
 
  for(int i=0; i<nums.size(); i++)
    if(nums[i] == true)	
      primes.push_back(i);
}  
 
int main() {
  sieve(MAX_PRIMES);
  
  return 0;
}
</file>

==== Implementation Notes ====
A C++ [[cpp_std_bitset|bitset]](([[http://www.cplusplus.com/reference/bitset/bitset/]])) is used for additional time/space efficiency to store true/false values. A [[cpp_std_vector|vector]] would also work, but at an increased cost of time and space.


==== Design Principles ====
Operation Sieve of Eratosthenes is quite simple. The sieve starts by assuming all numbers in a given range (2..n) are prime (''True'' values in our list). Then for each number, ''i'', from (2..sqrt(n)) we eliminate any multiples of ''i'' by setting them to ''False''.((We start the inner loop at i<sup>2</sup> to avoid many repeated assignments to the same array locations.)) After completion, the ''True'' values indicate indices that are prime (the list of which is generated by the final list comprehension in the ''return'' statement).

==== Analysis ====
The Sieve of Eratosthenes is not the fastest prime sieve available, but it is quick to code, easy to understand and modify, and sufficiently fast for some practical applications.

**Time Complexity:** %%O((n log n)(log log n))%%((http://primes.utm.edu/glossary/page.php?sort=SieveOfEratosthenes))\\
**Space Complexity:** %%O(n)%%

==== Benchmarks ====
This sieve should work reliably for primes up to 10<sup>6</sup> (Python3) or 10<sup>7</sup> (C++) in traditional contest settings.((All tests ran on an Intel(R) Xeon(R) X5550 CPU running at 2.67GHz.\\ Results are reported as user time in seconds using the bash builtin ''time'' command.))

^ %%n%%          ^ Python3((Python 3.5.2))         ^ C++((c++ -g -O2 -static -std=gnu++14 {files}))          ^
^ 10<sup>5</sup>    | .038s     | .000s        |
^ 10<sup>6</sup>    | .238s     | .008s |
^ 10<sup>7</sup>    | -     | .060s        |
^ 10<sup>8</sup>    | -     | .963        |

==== Example Problems ====
| Source | Problem | Difficulty((Difficulty rounded to the nearest 0.5.)) | Solutions (Spoilers) |
| Kattis | [[https://open.kattis.com/problems/happyprime| Happy Happy Prime Prime]] | 2.5/10 | [[http://cs1.utm.edu/icpc/doku.php?id=files:py:happyprime|happyprime.py]] |
| Kattis | [[https://open.kattis.com/problems/goldbach2| Goldbach's Conjecture]] | 3.5/10 | [[http://cs1.utm.edu/icpc/doku.php?id=files:py:goldbach2|goldbach2.py]] |
| Kattis | [[https://open.kattis.com/problems/primesieve|Prime Sieve]] | 5.0/10 | [[http://cs1.utm.edu/icpc/doku.php?id=files:cpp:primesieve|primesieve.cpp]] |

==== Source ====
Implementations are from the pseudocode provided in the Wikipedia article on the [[https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes|Sieve of Eratosthenes]]((Retrieved 08/08/2018)).
UT Martin Competitive Programming Guidebook

User Tools

Site Tools

Page Tools
