Get Math Help

GET TUTORING NEAR ME!

(800) 434-2582

By submitting the following form, you agree to Club Z!'s Terms of Use and Privacy Policy

    Home / Get Math Help

    Mathematical Algorithms

    Mathematical algorithms

    Euclidean algorithm | sieve of Eratosthenes

    Statements

    The Euclidean algorithm is an algorithm for finding the greatest common divisor of two numbers.

    The sieve of Eratosthenes is a simple algorithm for finding all prime numbers up to a specified integer. To apply the algorithm, sequentially write down the integers from 2 to the highest number n to be included in the table. Cross out all numbers greater than 2 which are divisible by 2, i.e., every second number. Find the smallest remaining number greater than 2, which is 3. Therefore, cross out all numbers greater than 3 which are divisible by 3, i.e., every third number. Find the smallest remaining number greater than 3. It is 5. Therefore, cross out all numbers greater than 5 which are divisible by 5, i.e., every fifth number. Continue until you have crossed out all numbers divisible by ⌊sqrt(n)⌋. Then the numbers remaining are prime.

    History

    | Euclidean algorithm | sieve of Eratosthenes formulation date | 300 BC (2323 years ago) | 250 BC (2273 years ago) formulators | Euclid | Eratosthenes status | proved | proved additional people involved | Gabriel Lamé | Nicomachus

    Common classes

    mathematical algorithms | solved mathematics problems

    Back to List | POWERED BY THE WOLFRAM LANGUAGE