Articles

2.1: The Sieve of Eratosthenes - Mathematics


A prime is an integer greater than 1 that is only divisible by 1 and itself. The integers 2, 3, 5, 7, 11 are prime integers. Note that any integer greater than 1 that is not prime is said to be a composite number.

The Sieve of Eratosthenes

The Sieve of Eratosthenes is an ancient method of finding prime numbers up to a specified integer. There are several other methods used to determine whether a number is prime or composite. We first present a lemma that will be needed in the proof of several theorems.

Every integer greater than one has a prime divisor.

We present the proof of this Lemma by contradiction. Suppose that there is an integer greater than one that has no prime divisors. Since the set of integers with elements greater than one with no prime divisors is nonempty, then by the well ordering principle there is a least positive integer (n) greater than one that has no prime divisors. Thus (n) is composite since (n) divides (n). Hence [n=ab mbox{with} 1

If (n) is a composite integer, then n has a prime factor not exceeding (sqrt{n}).

Since (n) is composite, then (n=ab), where (a) and (b) are integers with (1sqrt{n}), then

[sqrt{n}

and as a result

[ab>sqrt{n}sqrt{n}=n.]

Therefore (aleq sqrt{n}). Also, by Lemma 3, (a) must have a prime divisor (a_1) which is also a prime divisor of (n) and thus this divisor is less than (a_1 leq aleq sqrt{n}).

We now present the algorithm of the Sieve of Eratosthenes that is used to determine prime numbers up to a given integer.

The Algorithm of the Sieve of Eratosthenes

  1. Write a list of numbers from 2 to the largest number (n) you want to test. Note that every composite integer less than (n) must have a prime factor less than (sqrt{n}). Hence you need to strike off the multiples of the primes that are less than (sqrt{n})
  2. Strike off all multiples of 2 greater than 2 from the list . The first remaining number in the list is a prime number.
  3. Strike off all multiples of this number from the list.
  4. Repeat the above steps until no more multiples are found of the prime integers that are less than (sqrt{n})

Exercises

  1. Use the Sieve of Eratosthenes to find all primes less than 100.
  2. Use the Sieve of Eratosthenes to find all primes less than 200.
  3. Show that no integer of the form (a^3+1) is a prime except for (2=1^3+1).
  4. Show that if (2^n-1) is prime, then (n) is prime.
    Hint: Use the identity ((a^{kl}-1)=(a^{k}-1)(a^{k(l-1)}+a^{k(l-2)}+...+a^k+1)).

Sieve theory

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. The prototypical example of a sifted set is the set of prime numbers up to some prescribed limit X. Correspondingly, the prototypical example of a sieve is the sieve of Eratosthenes, or the more general Legendre sieve. The direct attack on prime numbers using these methods soon reaches apparently insuperable obstacles, in the way of the accumulation of error terms. [ citation needed ] In one of the major strands of number theory in the twentieth century, ways were found of avoiding some of the difficulties of a frontal attack with a naive idea of what sieving should be. [ citation needed ]

One successful approach is to approximate a specific sifted set of numbers (e.g. the set of prime numbers) by another, simpler set (e.g. the set of almost prime numbers), which is typically somewhat larger than the original set, and easier to analyze. More sophisticated sieves also do not work directly with sets per se, but instead count them according to carefully chosen weight functions on these sets (options for giving some elements of these sets more "weight" than others). Furthermore, in some modern applications, sieves are used not to estimate the size of a sifted set, but to produce a function that is large on the set and mostly small outside it, while being easier to analyze than the characteristic function of the set.


Wolfram Web Resources

The #1 tool for creating Demonstrations and anything technical.

Explore anything with the first computational knowledge engine.

Explore thousands of free applications across science, mathematics, engineering, technology, business, art, finance, social sciences, and more.

Join the initiative for modernizing math education.

Solve integrals with Wolfram|Alpha.

Walk through homework problems step-by-step from beginning to end. Hints help you try the next step on your own.

Unlimited random practice problems and answers with built-in Step-by-step solutions. Practice online or make a printable study sheet.

Collection of teaching and learning tools built by Wolfram education experts: dynamic textbook, lesson plans, widgets, interactive Demonstrations, and more.


Can the Sieve of Eratosthenes Build Lasting Fluency?

The term math facts is actually a pet peeve of mine. It makes me think of drills, repetitions, and timed quizzes. I prefer to think in terms of numeracy and fluency. If a student doesn’t know that 6ࡪ is 24, I want her to realize that it’s 4 more than 5ࡪ. Even if it means skip counting or using her fingers, better to use conceptual strategies than sit down and memorize a list. A list she’ll forget as soon as the quiz is over.

Referring to fluency in terms of ‘facts’ just feels disconnected. I want students to become fluent by developing number sense. Addition is the opposite of subtraction. Multiplication is repeated addition. To count up by nines, increase the tens place by one, and reduce the ones place by one.

This is where the Sieve comes in. The act of coloring in patterns creates a powerful understanding of the connections. If I count up by 7 five times, I get to 35. Counting down from 35 by 7’s still takes 5 steps. Wow, I guess multiplication and division must be connected!

If I want to add 77+8, I can go 1 row down (+10) and two boxes left (-2). That’s a handy shortcut I’ll remember next time I’m doing mental math.

When students learn ‘facts’ in context, it makes the math more interesting. It’s also a powerful way to help them remember what they’ve learned — even after the next summer break.


Find primes using Sieve of Eratosthenes

Sieve of Eratosthenes is a simple and ancient algorithm (over 2200 years old) used to find the prime numbers up to any given limit. It is one of the most efficient ways to find small prime numbers (<= $10^8$ ).

For a given upper limit the algorithm works by iteratively marking the multiples of primes as composite, starting from 2. Once all multiples of 2 have been marked composite, the muliples of next prime, ie 3 are marked composite. This process continues until $p < sqrt(N)$ where is a prime number.

This algorithm was devised by Eratosthenes, a greek mathematician, astronomer, poet, geographer. Erathosthenes was born in 276 BC, so this method was over 2200 years old. Therefore it is many times called the ancient efficient method for primes and it is still used heavily today.

Sift the Two's and Sift the Three's,
The Sieve of Eratosthenes.
When the multiples sublime,
The numbers that remain are Prime.

Pseudocode

The pseudocode of The sieve of Eratosthenes algorithm is as follows:

Example

Find list of prime numbers from 2 to 20

Visual Example

Complexity

The time and space complexity of The Sieve of Eratosthenes algorithm is as follows:

  • Worst case time complexity: Θ(N log log N)
  • Average case time complexity: Θ(N log log N)
  • Best case time complexity: Θ(N log log N)
  • Space complexity: Θ(N)

Implementations

Implementations of The Sieve of Eratosthenes algorithm in 9 different languages that is C, C++, C Sharp, Java, Go, Haskell, JavaScript, PHP and Python.


List/Chart/History(Background) of Prime Numbers

Ancient Greek mathematicians were the first to extensively study Prime Numbers and their properties. The mathematicians of Pythagoras's school (500 BC to 300 BC) were interested in Prime Numbers for their mystical and numerological properties. They understood the idea of primality and were interested in perfect and amicable numbers.

In 300 BC, when Euclid's Elements appeared, several important results about Prime Numbers were proved. Euclid proof of the Fundamental Theorem of Arithmetic explains that &ldquoEvery integer can be written as a product of Prime Numbers in an essentially unique way&rdquo.

In 200 BC, the Greek Eratosthenes devised an algorithm to calculate Prime Numbers, which in modern days is called the Sieve of Eratosthenes.

During the 17th Century, the next important developments in Prime Numbers were made by Fermat. Fermat's Little Theorem is the basis for many other results in Number Theory and is the basis for methods of checking whether numbers are prime which are still in use on today's electronic computers.

In 1952 the Mersenne numbers were proved to be prime by Robinson using an early computer and the electronic age had begun.

By 2018 a total of 50 Mersenne primes have been found.

Euler's work had a great impact on number theory in general and on Prime Numbers in particular.

Twin Prime Numbers

Prime Numbers that differ by 2 are known as Twin Prime Numbers
For example, a list of Prime Numbers between 1 to 10 is displayed below,

Let us consider the first two Prime Numbers in the above number line.
It is 2 and 3.
The difference between 2 and 3 is 1 (3 - 2 = 1)
Hence, 2 and 3 are not Twin Prime Numbers

Let us consider the second pair of Prime Numbers in the given number line.
It is 3 and 5.
The difference between 3 and 5 is 2 (5 - 3 = 2)
Hence, 3 and 5 are Twin Prime Numbers

Similarly let us try with the third pair of Prime Numbers in the given number line.
It is 5 and 7.
The difference between 5 and 7 is 2 (7 - 3 = 2)
Hence, 5 and 7 are Twin Prime Numbers

As the numbers keep increasing in the number line, Prime Numbers become less frequent and Twin Prime Numbers become rare to be found in the series.

Co-Prime Numbers

Co-prime numbers are a set of numbers which have only 1 as their common factor. Co means two, and hence in order to identify Co-Prime Numbers we will be in need of two numbers.
For Example
Let us consider the pair of numbers 18 and 35.
18 can be broken or in other words can be written as product of two numbers as below,
1 x 18 = 18
2 x 9 = 18
3 x 6 = 18
6 x 3 = 18
9 x 2 = 18
18 x 1 = 18
From the above list of product of two numbers, the Factors of 18 are 1, 2, 3, 6, 9 and 18

Let us work out the same for number 35, which is the pairing number to 18 in the given statement.
35 can be broken or in other words can be written as product of two numbers as below,
1 x 35 = 35
5 x 7 = 35
7 x 5 = 35
35 x 1 = 35
From the above list of product of two numbers, the Factors of 35 are 1, 5, 7 and 35

Comparing the factors of 18 and 35, 1 appears to be the only common factor, thus satisfying the property of a pair of numbers to be termed as Co-Prime Numbers.

Let us work out for another set of numbers to identify the difference between Co-Prime Numbers and Non Co-Prime Numbers.
In this case, let us take 18 and 19
The outcome is as shown in the below image,

As the only common Factor for numbers 18 and 19 is 1, Numbers 18 and 19 can be termed as Co-Prime Numbers.

Another Example,
In this case, let us take 18 and 20
Though 1 is a common Factor for 18 and 20, yet there is another common Factor in the list which is number 2.


The Property of a Co-Prime Number is that it should have only 1 as the Common Factor. In this case, we also have 2 along with 1 as Common Factor and hence numbers 18 and 20 are not Co-Prime in nature.

Interesting fact about 1 is that it is a Co-Prime Number for all the numbers.


2.1: The Sieve of Eratosthenes - Mathematics

It can be said that Eratosthenes is most widely known as a famous Greek mathematician. What most people probably do not know is that Eratosthenes is not only a famous mathematician but also a well known geographer, astronomer and historian.

Before I get into a few of his accomplishments, let me tell you a little about his personal history. Eratosthenes was born in Cyrene, Greece, which is now known as Libya, in North Africa, in 276 B.C.E.. It is believed that he starved himself to death in 195 B.C.E. due to the fact that he became blind and could no longer work. As a young man, Eratosthenes studied in Athens. Eventually, he made such a name for himself in his many fields that he caught the attention of the ruler of Egypt, Ptolemy III. Ptolemy III invited Eratosthenes to Alexandria, Egypt for two reasons to tutor his son and to be the librarian for the great Alexandrian University. Eratosthenes jumped at the chance. At the University, he was able to at most interested him and associate with other scholars. Now on to his accomplishments. . .

One of his major accomplishments in mathematics is his creation of a sieve that determines prime numbers up to any given limit. This sieve, which is called, the Sieve of Eratosthenes, is still important today in number research theory. Prime numbers are natural numbers greater than 1 that can be divided without remainder only by itself and by 1. Eratosthenes figured out that if you were to write down all the natural numbers from 2 to infinity and "sieve out" every second number after two (or multiples of two), then move to the next available number (3) and continue to "sieve out" every multiple of 3 and so on, one would end up with a list of prime numbers.

Eratosthenes is also known for his achievement in astronomy. Several astronomers and mathematicians before and after Eratosthenes tried to accurately measure the circumference of the Earth, but is was Eratosthenes that came through. He found the circumference of the Earth to be nearly 250,000 stadia (25,000 miles). Eratosthenes observed that the sun shone directly down a well at high noon on the day of the summer solstice in Syene and that it cast a shadow in Alexandria, directly south of where the well was. To calculate the circumference of the Earth, Eratosthenes measured the angle of the shadow to the Earth. Until he realized this, Eratosthenes believed that the sun was so far away that its rays were parallel. It is also believed that Eratosthenes made a star catalog with approximately 675 stars and created a calendar that included leap years.

As a historian, Eratosthenes decided to work on giving a systematic chronography of the known world by figuring out the dates of literary and political events from the siege of Troy up until his time. However, this was only a beginning. Others built on his foundation.

There is still more. Eratosthenes also contributed to geographic source of the river. Many scholars that preceded Eratosthenes in the study of the Nile river, tried to figure out the reason why parts of the river flooded while other parts did not. It was not until Eratosthenes that a correct answer was proposed. He believed that heavy rains near the source of the Nile was the cause of Many of Eratosthenes' peers nicknamed him "Beta" which is the second letter of the Greek alphabet, indicating that he just fell short of first place. Eratosthenes contributed greatly to many different areas of knowledge, more than I could cover in this short paper. Maybe in his time period, his peers did not feel that he contributed enough in one area or maybe they were jealous that he had contributed so much to so many areas. For a man who was nicknamed Beta, it is pretty impressive that so much of his work in these areas is still discussed today, so many years later.


Definitions

  • A number is prime if it has exactly two positive whole number divisors, one and itself.
  • A number is composite if it has more than two positive whole number divisors.

That means there exists numbers that are neither prime nor composite such as 0, 1 and any non-whole numbers.

Prime numbers are fascinating because there is no pattern or formula to predict them. The larger they get, the more difficult they are to find because the list of possible numbers they cannot be divided by grows. Needless to say, really large prime numbers are few and far between.

Currently, the largest known prime number was found in 2013 and is 17,425,170 digits long! The number is so big that it is recorded as:

Mathematicians call primes that are one less than a power of 2 (like the one above) Mersenne Primes, named after 17th century French mathematician, music theorist, and Minim Friar Marin Mersenne.

Discovering a new prime number is a noteworthy accomplishment and could even win you a small fortune. The Electronic Frontier Association promises to award $150k to the first person or group who discovers a prime number at least 100,000,000 digits long and $250k to the first person or group who discovers a prime number at least 1,000,000,000 digits.

How do we know primes this big even exist?

In the next lesson, I’ll show you how we know that there exists an infinite quantity of prime numbers. So stay tuned!

Let’s find the first 25 prime numbers. To do this we’ll use a technique pioneered by ancient Greek mathematician Eratosthenes.

(Note: If you have children, this is a great introductory exercise. See if you can help them figure out how to eliminate numbers to find the primes.)


Python Math: Print all primes (Sieve of Eratosthenes) smaller than or equal to a specified number

Write a Python program to print all primes (Sieve of Eratosthenes) smaller than or equal to a specified number.

In mathematics, the sieve of Eratosthenes, one of a number of prime number sieves, is a simple, ancient algorithm for finding all prime numbers up to any given limit. It does so by iteratively marking as composite (i.e., not prime) the multiples of each prime, starting with the multiples of 2.

Pictorial presentation:

Animation Credits: Author information here

Sample Solution:-

Python Code:



Basic Number Theory-2

The concept of prime numbers is a very important concept in math. This article discusses the concept of prime numbers and related properties.

What are prime numbers and composite numbers?

Prime numbers are those numbers that are greater than 1 and have only two factors 1 and itself.

Composite numbers are also numbers that are greater than 1 but they have at least one more divisor other than 1 and itself.

For example, 5 is a prime number because 5 is divisible only by 1 and 5 only. However, 6 is a composite number as 6 is divisible by 1, 2, 3, and 6.

There are various methods to check whether a number is prime.

Naive approach

Traverse all the numbers from $1$ to $N$ and count the number of divisors. If the number of divisors is equal to 2 then the given number is prime, else it is not.

The time complexity of this function is O(N) because you traverse from $1$ to $N$.

Better approach

If you have two positive numbers $N$ and $D$, such that $N$ is divisible by $D$ and $D$ is less than the square root of $N$.

  • $(N / D)$ must be greater than the square root of $N$.
  • $N$ is also divisible by $(N/D)$. If there is a divisor of $N$ that is less than the square root of $N$, then there will be a divisor of $N$ that is greater than square root of $N$. You will have to traverse till the square root of $N$.

Note: You are generating all the divisors of $N$ and if the count of divisors is greater than 2, then the number is composite.

For example, if N=50, $sqrt N$=7 (floor value). You will iterate from 1 to 7 and count the number of divisors of N. The divisors of $N$ are 1, 50 2, 25 5,10. You have 6 divisors of 50, and therefore, it is not prime.

The time complexity of this function is $O(sqrt N)$ because you traverse from 1 to $sqrt N$.

Sieve of Eratosthenes

You can use the Sieve of Eratosthenes to find all the prime numbers that are less than or equal to a given number N or to find out whether a number is a prime number.

The basic idea behind the Sieve of Eratosthenes is that at each iteration one prime number is picked up and all its multiples are eliminated. After the elimination process is complete, all the unmarked numbers that remain are prime.

  1. Mark all the numbers as prime numbers except 1
  2. Traverse over each prime numbers smaller than sqrt(N)
  3. For each prime number, mark its multiples as composite numbers
  4. Numbers, which are not the multiples of any number, will remain marked as prime number and others will change to composite numbers.

This code will compute all the prime numbers that are smaller than or equal to N.

Let us compute prime numbers where $N = 10$.

In each iteration, check if a number is prime or not, if it is then mark all of its multiple as composite.

The prime numbers are 2, 3, 5, and 7.

Time complexity
The inner loop that runs for each element is as follows:

  1. If i = 2, inner loop runs N / 2 times
  2. If i = 3, inner loop runs N / 3 times
  3. If i = 5, inner loop runs N / 5 times

Reference for complexity analysis: Sieve of Erastothenes

Modification of Sieve of Eratosthenes for fast factorization

When you exit the for loop, $res vector $ is the factorization of $N=50$.

At every step, you must look for the prime number of the least value, which divides the current $N$. This is the main idea of this modification.

Let us construct an array which will give us this number in O(1) time.

Now, use this modification to factorize $N$ in O(log(N)) time.

The required factors are in $res$ .

You can implement this modification only if you are allowed to create an array of integers of size $N$.

Note: This approach is useful when you need to factorize not-very-large numbers. It is not necessary to build a modified Sieve for every problem in which factorization is required. Moreover, you cannot build it for large numbers $N$ like $10^9$ or $10^<12>$. Therefore, for such large numbers it is recommended that you factorize in O(sqrt(N)) instead.

If the factorization of $N$ is $p_1^ * p_2^ * . * p_k^$ where $p_1,p_2$. $p_k$ are the prime factors of $N$ and $q_1,q_2$. $q_k$ are the powers of the respective prime factors, then $N$ has $(q_1+ 1) * (q_2+ 1) * . * (q_k + 1)$ distinct divisors.

Sieve of Eratosthenes on the segment:

Sometimes you need to find all the primes that are in the range $[L. R]$ and not in $[1. N]$, where $R$ is a large number.

You are allowed to create an array of integers with size $(R - L + 1)$.

Implemention

The approximate comlexity is O(sqrt(R))

Suggestions

It is recommended that you do not build a Sieve to check several numbers for primality. Use the following function instead, which works in $O(sqrt N)$ for every number:


The Sieve of Eratosthenes

Solve problems by finding the prime factors of numbers.

Eratosthenes, who lived in Greece from about 276 to 195 BC, invented a system to find prime numbers. It consists of crossing out every second number except 2 on a grid then every third number except 3, and so on. The numbers not crossed out are prime. (A discussion about 1 being a special number in that it is neither prime nor non-prime may be worthwhile.)

Using Materials

Give each student a copy of the grid. Notice the number 1 is shaded to indicate it is special. 2 is prime and ringed. Discuss how to cross out all the multiples of 2. (Answer: For example cross out whole columns at a time.)

Ring 3 and cross out all multiples of 3 (that is 6, 9, 12 . ). Ring 5 and cross out multiples of 5. Continue until all the prime numbers ≤ 200 are ringed.

Discussion: Why is this called a sieve?

Understanding Number Properties:

Describe how you would determine whether 349 is prime using the Sieve of Eratosthenes. Don’t actually do it. Is the method generally useful? Consider for example, testing whether 179 781 is prime.


Watch the video: Κόσκινο για ελιές πατέντα χωρίς κόστος (October 2021).