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:53]
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 54: Line 52:
 </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 75: Line 73:
 ^ 10<sup>7</sup>    | -     | .060s        | ^ 10<sup>7</sup>    | -     | .060s        |
 ^ 10<sup>8</sup>    | -     | .963        | ^ 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.1533848008.txt.gz ยท Last modified: 2018/08/09 15:53 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