Differences

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

--- algorithms_primes [2018/08/09 09:16]
jguerin Need to take benchmarks off of CS1.
+++ — (current)
@@ Line 1: / Line 1: @@
-====== Algorithms: Prime Numbers ======
-===== Prime Sieves =====
-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.
-== 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.
-==== Sieve of Eratosthenes ====
-<file python sieve.py>
-from math import *
-def sieve(n):
-    primes = [True] * (n+1)                             # generate a list of primes
-    primes[0] = primes[1] = False
-    for i in range(2, int(sqrt(n))+1):                  # filter out non-primes
-        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 <iostream>
-#include <vector>
-using namespace std;
-const int MAX_PRIMES=10000000;
-vector<int>sieve(int n) {
-  bitset<MAX_PRIMES+1> nums;      // generate a list of primes
-  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
-    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++)
-    if(nums[i] == true)
-      primes.push_back(i);
-  return primes;
-}
-int main() {
-  vector<int> primes = sieve(MAX_PRIMES);
-  return 0;
-}
-</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 ===
-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.
-=== 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 implementation (Python3) should work reliably for primes up to 10<sup>6</sup> in competition settings.
-^ %%n%%          ^ Python3         ^ C++          ^
-| 10<sup>5</sup>    | .054s     | .166        |
-| 10<sup>6</sup>    | .562s     | .166 |
-| 10<sup>7</sup>    | -     | .166        |
-Redo benchmarks on desktop.
-=== 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