Sieve of Sundaram

Sieve of Sundaram

In mathematics, the sieve of Sundaram is a simple deterministic algorithm for finding all prime numbers up to a specified integer. It was discovered by an Indian student S. P. Sundaram from Sathyamangalam in 1934. [cite journal |author=V. Ramaswami Aiyar |title=Sundaram's Sieve for Prime Numbers |journal=The Mathematics Student |volume=2 |number=2 |year=1934 |pages=73 |issn=0025-5742] [cite journal |author=G.|title=Curiosa 81. A New Sieve for Prime Numbers |journal=Scripta Mathematica |volume=8 |number=3 |year=1941 |pages=164]

Algorithm

A list of the positive integers is made. From this list, remove all numbers of the form of "i" + "j" + 2"ij" where "i" and "j" are positive integers (and "j" <= "i", to exclude trivial duplicates).

The remaining numbers are doubled and incremented by one, giving a list of the odd prime numbers (i.e., all primes except the only even prime 2).

Correctness

If the expression "i" + "j" + 2"ij" is doubled and incremented, we have

2("i" + "j" + 2"ij") + 1

= 2"i" + 2"j" + 4"ij" + 1

= (2"i" + 1)(2"j" + 1).

Thus all the numbers excluded from the doubled-and-incremented list are composite, because both factors in (2"i" + 1)(2"j" + 1) are greater than 1. If a number is prime, it cannot be placed into that factorization for any positive "i", "j", and so is left in the list.

ee also

* Primality test
* General number field sieve
* Sieve theory

References

*
*
* [http://www.primzahlsuche.de/intro.html#sieve2 A new "sieve" for primes] , an excerpt from cite book |last=Kordemski |first=Boris A. |title=Köpfchen, Köpfchen! Mathematik zur Unterhaltung|publisher=Urania Verlag| year=1974 |series=MSB Nr. 78 | pages=pp. 200 (translation of Russian book cite book |last=Кордемский |first=Борис Анастасьевич |title=Математическая смекалка |publisher=М.: ГИФМЛ |year=1958 |url=http://ilib.mirror1.mccme.ru/djvu/klassik/smekalka.htm)
*
*
*


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Sieve of Eratosthenes — Sieve of Eratosthenes: algorithm steps for primes below 121 (including optimization of starting from prime s square). In mathematics, the sieve of Eratosthenes (Greek: κόσκινον Ἐρατοσθένους), one of a number of prime number sieves, is a simple,… …   Wikipedia

  • Quadratic sieve — The quadratic sieve algorithm (QS) is a modern integer factorization algorithm and, in practice, the second fastest method known (after the general number field sieve). It is still the fastest for integers under 100 decimal digits or so, and is… …   Wikipedia

  • General number field sieve — In number theory, the general number field sieve (GNFS) is the most efficient classical algorithm known for factoring integers larger than 100 digits. Heuristically, its complexity for factoring an integer n (consisting of log2 n bits) is of …   Wikipedia

  • List of mathematics articles (S) — NOTOC S S duality S matrix S plane S transform S unit S.O.S. Mathematics SA subgroup Saccheri quadrilateral Sacks spiral Sacred geometry Saddle node bifurcation Saddle point Saddle surface Sadleirian Professor of Pure Mathematics Safe prime Safe… …   Wikipedia

  • Multiplication algorithm — A multiplication algorithm is an algorithm (or method) to multiply two numbers. Depending on the size of the numbers, different algorithms are in use. Efficient multiplication algorithms have existed since the advent of the decimal system.… …   Wikipedia

  • Discrete logarithm — In mathematics, specifically in abstract algebra and its applications, discrete logarithms are group theoretic analogues of ordinary logarithms. In particular, an ordinary logarithm loga(b) is a solution of the equation ax = b over the… …   Wikipedia

  • Primality test — A primality test is an algorithm for determining whether an input number is prime. Amongst other fields of mathematics, it is used for cryptography. Unlike integer factorization, primality tests do not generally give prime factors, only stating… …   Wikipedia

  • AKS primality test — The AKS primality test (also known as Agrawal–Kayal–Saxena primality test and cyclotomic AKS test) is a deterministic primality proving algorithm created and published by three Indian Institute of Technology Kanpur computer scientists, Manindra… …   Wikipedia

  • Dixon's factorization method — In number theory, Dixon s factorization method (also Dixon s random squares method[1] or Dixon s algorithm) is a general purpose integer factorization algorithm; it is the prototypical factor base method, and the only factor base method for which …   Wikipedia

  • Miller–Rabin primality test — The Miller–Rabin primality test or Rabin–Miller primality test is a primality test: an algorithm which determines whether a given number is prime, similar to the Fermat primality test and the Solovay–Strassen primality test. Its original version …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”