China
Africa
Explore chapters and articles related to this topic
Number Theory
Published in Paul L. Goethals, Natalie M. Scala, Daniel T. Bennett, Mathematics in Cyber Research, 2022
The Sieve of Eratosthenes is an ancient and surprisingly efficient algorithm for generating a list of all primes up to a given bound n. The Sieve of Eratosthenes requires O(n) storage and has time-complexity O(nlognloglogn). It proceeds as follows: Begin with the array of all integers from 2 to n.For primes p=2,3,…, mark as composite all multiples of p between p2 and n.Stop when p2>n.
Combinatorics
Published in Sriraman Sridharan, R. Balakrishnan, Foundations of Discrete Mathematics with Algorithms and Programming, 2019
Sriraman Sridharan, R. Balakrishnan
Algorithm: Write down the list of all integers from 2 to n. Let p1=2,p2=5,…,pm $ p_1=2,p_2=5,\ldots ,p_m $ be the known prime numbers ≤n $ \le \sqrt{n} $ . Now strike out the numbers of the list which are divisible by p1 $ p_1 $ , then strike out the numbers divisible by p2 $ p_2 $ , and so on, and finally strike out the numbers divisible by pm $ p_m $ . By the Fact 1.9.2.1, the numbers remaining in the list are all prime numbers >n $>\sqrt{n} $ and ≤n $ \le n $ . This method of generating prime numbers is known as the “sieve of Eratosthenes.”
S
Published in Phillip A. Laplante, Dictionary of Computer Science, Engineering, and Technology, 2017
sieve of Eratosthenes an algorithm to find all prime numbers up to a certain N. Begin with an (unmarked) array of integers from 2 to N. The first unmarked integer, 2, is the first prime. Mark every multiple of this prime. Repeatedly take the next unmarked integer as the next prime and mark every multiple of the prime.
Fostering collateral creativity through teaching school mathematics with technology: what do teachers need to know?
Published in International Journal of Mathematical Education in Science and Technology, 2022
What is a prime number? One of the definitions is as follows: Prime number is a natural number greater than 1 which is not a product of smaller natural numbers. How can one find such numbers? The first number satisfying the definition is 2. It is a product of two numbers, 1 and 2, but only 1 is smaller than 2. The same can be said about 3. It is a product of two numbers 1 and 3, but only 1 is smaller than 3. Yet the number 4 is not a prime as it can be written as a product of two 2’s. In the 3rd century B.C., a Greek scholar Eratosthenes devised a method (nowadays called the sieve of Eratosthenes; the term sieve used in the previous section was borrowed from this context) of separating primes from natural numbers by continuously eliminating all multiples of 2, then all multiples of 3, then all multiples of 5 (the third prime number), then all multiples of 7 (as 7 is the first number to survive elimination by 2, 3, and 5), and so on.