 In mathematics, the Sieve of Eratosthenes is a simple, ancient algorithm for finding all prime numbers up to a specified integer. It is the predecessor to the modern Sieve of Atkin, which is faster but more complex. It was created by Eratosthenes, an ancient Greek mathematician. Wheel factorization is often applied on the list of integers to be checked for primality, before Sieve of Eratosthenes is used, to increase the speed. Image File history File links No higher resolution available. ...
For other meanings of mathematics or uses of math and maths, see Mathematics (disambiguation) and Math (disambiguation). ...
In mathematics, computing, linguistics, and related disciplines, an algorithm is a finite list of well-defined instructions for accomplishing some task that, given an initial state, will terminate in a defined end-state. ...
In mathematics, a prime number (or a prime) is a natural number which has exactly two distinct natural number divisors: 1 and itself. ...
In mathematics, the sieve of Atkin is a fast, modern algorithm for finding all prime numbers up to a specified integer. ...
This article is about the Greek scholar of the third century BC. For the ancient Athenian statesman of the fifth century BC, see Eratosthenes (statesman). ...
The term ancient Greece refers to the periods of Greek history in Classical Antiquity, lasting ca. ...
Leonhard Euler, considered one of the greatest mathematicians of all time A mathematician is a person whose primary area of study and research is the field of mathematics. ...
In number theory, wheel factorization is a type of sieve where numbers are written around circles in a specific manner for the sieve to operate. ...
Algorithm - Write a list of numbers from 2 to the largest number you want to test for primality. Call this List A. (This is the list of squares on the left-hand-side of the picture.)
- Write the number 2, the first prime number, in another list for primes found. Call this List B. (This is the list on the right-hand-side of the picture.)
- Strike off 2 and all multiples of 2 from List A.
- The first remaining number in the list is a prime number. Write this number into List B.
- Strike off this number and all multiples of this number from List A. The crossing-off of multiples can be started at the square of the number, as lower multiples have already been crossed out in previous steps.
- Repeat steps 4 and 5 until no more numbers are left in List A.
The following is pseudocode for the algorithm: Pseudocode (derived from pseudo and code) is a compact and informal high-level description of a computer programming algorithm that uses the structural conventions of programming languages, but omits detailed subroutines, variable declarations or language-specific syntax. ...
In mathematics, computing, linguistics, and related disciplines, an algorithm is a finite list of well-defined instructions for accomplishing some task that, given an initial state, will terminate in a defined end-state. ...
// arbitrary search limit limit ← 1.000.000 // assume all numbers are prime at first is_prime(i) ← true, i ∈ [2, limit] for n in [2, √limit]: if is_prime(n): // eliminate multiples of each prime, // starting with its square is_prime(i) ← false, i ∈ {n², n²+n, n²+2n, ..., limit} for n in [2, limit]: if is_prime(n): print n Or, more simplified: limit = 1000000 sieve$ = string of the character "P" with length limit prime = 2 repeat while prime2 < limit set the character at the index of each multiple of prime (excluding index prime * 1) in sieve$ to "N" prime = index of the next instance of "P" in sieve$ after index prime end repeat print the index of each instance of "P" in sieve$
See also A primality test is an algorithm for determining whether an input number is prime. ...
In mathematics, the general number field sieve (GNFS) is the most efficient algorithm known for factoring integers larger than 100 digits. ...
Sieve theory is a set of general techniques in number theory, designed to count, or more realistically to estimate the size of, sifted sets of integers. ...
References - Κοσκινον Ερατοσθενους or, The Sieve of Eratosthenes. Being an Account of His Method of Finding All the Prime Numbers, by the Rev. Samuel Horsley, F. R. S., Philosophical Transactions (1683-1775), Vol. 62. (1772), pp. 327-347.
External links - Analyze the Sieve of Eratosthenes in an online Javascript IDE
|
Feeds |
Contact