UT Martin Competitive Programming Guidebook

User Tools

Site Tools

Trace:
algorithms:sieve:eratosthenes

Differences

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

Link to this comparison view

Both sides previous revision Previous revision
Next revision 		Previous revision
algorithms:sieve:eratosthenes [2018/08/09 15:37]
jguerin Python sieve speed up (check bit before entering second loop). 		algorithms:sieve:eratosthenes [2018/08/20 13:58] (current)
jguerin Minor wording tweak.
Line 1: Line 1:
 ====== Prime Number Generator: Sieve of Eratosthenes  ====== ====== Prime Number Generator: Sieve of Eratosthenes  ======
  
-Prime sieves 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 ranging up to 10<sup>6</sup> or greater), in particular when many such verifications may be necessary.+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.
  
-== Etymology == 
-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. 
  
 ===== Source ===== ===== Source =====
Line 11: Line 9:
  
 def sieve(n): def sieve(n):
-    primes = [True] * (n+1)                             # generate a list of primes+    primes = [True] * (n+1)                             # true for each primes
     primes[0] = primes[1] = False     primes[0] = primes[1] = False
     for i in range(2, int(sqrt(n))+1):                  # filter out non-primes     for i in range(2, int(sqrt(n))+1):                  # filter out non-primes
Line 25: Line 23:
 #include <bitset> #include <bitset>
 #include <cmath> #include <cmath>
-#include <iostream> 
 #include <vector> #include <vector>
  
 using namespace std; using namespace std;
 + 
 +const int MAX_PRIMES=100000000;
  
-const int MAX_PRIMES=10000000;+bitset<MAX_PRIMES+1> nums;        // true for each prime 
 +vector<int> primes;               // list of primes
  
-vector<int>sieve(int n) { +void sieve(int n) {
-  bitset<MAX_PRIMES+1> nums;      // generate a list of potential primes+
   nums.set();                     // set all values to true   nums.set();                     // set all values to true
   nums[0] = nums[1] = false;   nums[0] = nums[1] = false;
   for(int i=2; i<=sqrt(n)+1; i++) // filter out non-primes   for(int i=2; i<=sqrt(n)+1; i++) // filter out non-primes
-    for(int j=i*i; j<n+2; j+=i)  +    if(nums[i]) 
-      nums[j] = false; +      for(int j=i*i; j<n+2; j+=i)  
- + nums[j] = false; 
-  vector<int> primes;              // generate primes from true values+ 
   for(int i=0; i<nums.size(); i++)   for(int i=0; i<nums.size(); i++)
     if(nums[i] == true)      if(nums[i] == true)
       primes.push_back(i);       primes.push_back(i);
- 
-  return primes; 
 }   }  
 + 
 int main() { int main() {
-  vector<int> primes = sieve(MAX_PRIMES); +  sieve(MAX_PRIMES); 
 +  
   return 0;   return 0;
 } }
 </file> </file>
  
-=== Implementation Notes ===+==== 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. 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.
  
Line 69: Line 66:
  
 ==== Benchmarks ==== ==== Benchmarks ====
-The Python3 implementation should work reliably for primes up to 10<sup>6</sup> in competition settings. The C++ implementation should work reliably for primes up to 10<sup>7</sup> in 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.))+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}))          ^ ^ %%n%%          ^ Python3((Python 3.5.2))         ^ C++((c++ -g -O2 -static -std=gnu++14 {files}))          ^
-^ 10<sup>5</sup>    | .054s     | .000s        | +^ 10<sup>5</sup>    | .038s     | .000s        | 
-^ 10<sup>6</sup>    | .562s     | .011s | +^ 10<sup>6</sup>    | .238s     | .008s | 
-^ 10<sup>7</sup>    | -     | .167s        |+^ 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 ==== ==== 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)). 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)).
  
algorithms/sieve/eratosthenes.1533847060.txt.gz · Last modified: 2018/08/09 15:37 by jguerin

Page Tools

Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Noncommercial-Share Alike 4.0 International
CC Attribution-Noncommercial-Share Alike 4.0 International Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki