Differences

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

--- algorithms_primes [2018/08/08 14:43]
jguerin Added complexity analysis.
+++ — (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>
-def sieve(n):
-    assert n > 1
-    primes = [True] * (n+1)
-    primes[0] = primes[1] = False
-    for i in range(2, int(sqrt(n))+1):
-        for j in range(i**2, n+1, i):
-            primes[j] = False
-    return [i for i in range(len(primes)) if primes[i]]
-</file>
-=== Design and Principles ===
-=== 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 should work reliably for primes up to 10<sup>6</sup> in competition settings.

UT Martin Competitive Programming Guidebook

User Tools

Site Tools

Differences

Page Tools