Differences

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

--- algorithms:sieve:eratosthenes [2018/08/09 15:46]
jguerin Updated C++ code.
+++ algorithms:sieve:eratosthenes [2018/08/20 13:58] (current)
jguerin Minor wording tweak.
@@ Line 1: / Line 1: @@
 ====== 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 =====
@@ Line 54: / Line 52: @@
 </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.
@@ Line 68: / Line 66: @@
 ==== 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}))          ^
-^ 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 ====
 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

Differences

Page Tools