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 11:13]
jguerin 		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
-        for j in range(i**2, n+1, i): +        if primes[i]: 
-            primes[j] = False+            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     return [i for i in range(len(primes)) if primes[i]] # generate primes from True values
 + 
 primes = sieve(1000000) primes = sieve(1000000)
 </file> </file>
Line 24: 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 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>
- 
-==== 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). 
  
 ==== 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.
  
 +
 +==== 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 ==== ==== Analysis ====
Line 68: 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.1533831228.txt.gz · Last modified: 2018/08/09 11:13 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