G
Guest
Guest
How do I find all the prime numbers less than 100 using the Sieve of Eratosthenes?
* The Fundamental Theorem of Arithmetic states that every positive integer/number greater than 1 is either prime or composite and can be written uniquely as a product of primes, with the prime factors in the product written in order of nondecreasing size.
* A prime number is a positive number "p" that has but two positive divisors/factors, 1 and "p".
(The strict interpretation of this definition aids in supporting the statement that the number one is not a prime number as it is the only number with one divisor/factor whereas a prime always has two factors.)
Examples: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, etc., are all primes, being evenly divisible by only 1 and the number itself.
* A composite number is therefore any number that has 3 or more factors/divisors.
* The number 1 is not considered a prime number, being more traditionally referred to as the unit.
Aristotle regarded the one as not being a number but rather the elemental measure, or building block, of all numbers.
Euclid stated that a unit is that property of each and every thing in the universe that enables it to be called one, while a number can be considered a multitude of units.
Thymaridas called the unit the limiting quantity or limit of fewness.
Some ealy definitions of number were
......-- a collection of units
......-- a progression of multitude starting with the unit
......-- a determinate multitude
......-- limited multitude
......-- a multitude of units
......-- several ones
......-- a multitude measureable by one
Every number N contains N ones or units.
* A composite number is expressable as a unique product of prime numbers and their exponents, in only one way.
Examples: 210 = 2x3x5x7; 495 = 3^2x5x11.
* A prime factor of a number is a divisor/factor of the number which also happens to be a prime number. The factors of 36 are 1, 2, 3, 4, 6, 9, 12, 18 and 36 but only 2 and 3 are prime factors.
* The number 1 is the only number that is a factor of all other numbers.
* Any number that can be expressed as the product of two or more primes and their powers, i.e., ab, abc, ab^2c, ab^2c^3d^2, etc., where a, b, c and d are prime numbers, is composite.
* Any number greater than 1 that is not a prime number must be a composite number, and is the result of multiplying primes together.
Examples: 4, 6, 12, 24, 72, etc., are composite, each being divisible by lower prime numbers.
* Every number n > 1 is divisible by some prime.
* With the exception of the number 2, all prime numbers are odd numbers.
The number 2 is the only even prime, thereby making it the oddest prime.
* All prime numbers of two digits or more end in 1, 3, 7, or 9.
Caution: There are numbers that end in 1, 3, 7, or 9 that are not prime but, in order to be a prime, it must end in 1, 3, 7, or 9.
* Two integers are said to be relatively prime, or prime to each other, if their greatest common divisor is 1.
Examples: 7 and 12 are relatively prime as their g.c.d. is 1 or (7,12) = 1.
* A semi-prime number is one that has exactly two prime factors in addition to the factors of one and the number itself. For example, 6, 10, 14, 15, 21, 39, 142, 143, etc. are semi-prime numbers. By definition, such numbers are also classified as composite numbers.
* Primes differing by 2 are called twin primes.
Examples: 3-5, 5-7, 11-13, 17-19, 29-31, 41-43, 59-61, 71-73, 101-103, 1,000,000,009,649-1,000,000,009,651.
* The sums of all pairs of twin primes (except 3-5) are divisible by 12.
* There is only one set of triple primes - 3, 5, and 7.
* The prime number 5 is the only prime number that is both the sum and difference of two other primes.
* The primes 2 and 3 are ofter referred to as the Siamese Twins as they are the only two adjacent prime numbers.
* Every odd number is congruent to either 1 or 3 modulo(4) meaning that every odd number minus 1 or 3 is divisible by 4.
* Every prime number is congruent to one of 1, 2, 3 or 4 modulo(5).
* There are infinitely many primes of the form N^2 + 1. If of the form N^2 + 1, it does not mean it is automatically prime. Primes of the form N^2 + 1 are either prime or the product of two primes.
* Every prime of the form 4n + 1 can be written as the sum of two squares, 5, 13, 17, 29, 37, 41, 53, etc.
* No primes of the form 4n - 1 can be written as the sum of two squares, 3, 7, 11, 43, 47, 59, 67, etc.
* The number 17 is the only prime that is equal to the sum of the digits of its cube.
* A prime p is the sum of two squares if, and only if, p + 1 is not divisible by 4.
Finding Primes
The Sieve of Eratosthenes
Lets find the primes between 1 and 100.
Write down the sequence of numbers from 1 to 100.
Cross out the 1.
Beginning with the 2, strike out every second number beyond the 2, i.e., 4, 6, 8, 10, etc.
Starting from the first remaining number, 3, cross out every third number beyond the 3, i.e., 3, 6, 9, 12, etc.
Starting from the first remaining number, 5, cross out every fifth number beyond the 5, i.e., 5, 10, 15, 20, etc.
Continue with the 7, crossing out every seventh number beyond the 7, i.e., 7, 14, 21, 28, etc.
Continue the process until you have reached N or 100.
The numbers remaining are the primes between 1 and 100, namely 2, 3, 5, 7, 11, 13,17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, and 97. By definition, all the others are composite numbers.
The Sieve of Sundaram
Given the infinite table of p rows and q columns.
.4....7....10...13...16...19...22...25....28....52...57...etc.. constant 3 difference
.7...12...17...22...27...32...37...42....47....52...57...etc constant 5 difference
10..17...24...31...38...45...52...59....66....73...80...etc. constant 7 difference
13..22...31...40...49...58...67...76....85....94..103..etc. constant 9 difference
16..27...38...49...60...71...82...93...104..115..126..etc. constant 11 difference
19..32...45...58...71...84...97..110..123..136..149..etc constant 13 difference
Required to determine if the number N is prime or composite.
Let k = (N - 1)/2
If the value of k is found in the table, N is composite.
If the value of k is not found in the table, N is prime.
The 1st number in the pth row is given by 3p + 1
The successive difference in each row is given by 2q + 1
The qth number in the pth row is there defined as (2q + 1)p + q
Therefore, if values of p and q can be found to make (2q + 1)p + q = k, N is not a prime.
* A prime number is a positive number "p" that has but two positive divisors/factors, 1 and "p".
(The strict interpretation of this definition aids in supporting the statement that the number one is not a prime number as it is the only number with one divisor/factor whereas a prime always has two factors.)
Examples: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, etc., are all primes, being evenly divisible by only 1 and the number itself.
* A composite number is therefore any number that has 3 or more factors/divisors.
* The number 1 is not considered a prime number, being more traditionally referred to as the unit.
Aristotle regarded the one as not being a number but rather the elemental measure, or building block, of all numbers.
Euclid stated that a unit is that property of each and every thing in the universe that enables it to be called one, while a number can be considered a multitude of units.
Thymaridas called the unit the limiting quantity or limit of fewness.
Some ealy definitions of number were
......-- a collection of units
......-- a progression of multitude starting with the unit
......-- a determinate multitude
......-- limited multitude
......-- a multitude of units
......-- several ones
......-- a multitude measureable by one
Every number N contains N ones or units.
* A composite number is expressable as a unique product of prime numbers and their exponents, in only one way.
Examples: 210 = 2x3x5x7; 495 = 3^2x5x11.
* A prime factor of a number is a divisor/factor of the number which also happens to be a prime number. The factors of 36 are 1, 2, 3, 4, 6, 9, 12, 18 and 36 but only 2 and 3 are prime factors.
* The number 1 is the only number that is a factor of all other numbers.
* Any number that can be expressed as the product of two or more primes and their powers, i.e., ab, abc, ab^2c, ab^2c^3d^2, etc., where a, b, c and d are prime numbers, is composite.
* Any number greater than 1 that is not a prime number must be a composite number, and is the result of multiplying primes together.
Examples: 4, 6, 12, 24, 72, etc., are composite, each being divisible by lower prime numbers.
* Every number n > 1 is divisible by some prime.
* With the exception of the number 2, all prime numbers are odd numbers.
The number 2 is the only even prime, thereby making it the oddest prime.
* All prime numbers of two digits or more end in 1, 3, 7, or 9.
Caution: There are numbers that end in 1, 3, 7, or 9 that are not prime but, in order to be a prime, it must end in 1, 3, 7, or 9.
* Two integers are said to be relatively prime, or prime to each other, if their greatest common divisor is 1.
Examples: 7 and 12 are relatively prime as their g.c.d. is 1 or (7,12) = 1.
* A semi-prime number is one that has exactly two prime factors in addition to the factors of one and the number itself. For example, 6, 10, 14, 15, 21, 39, 142, 143, etc. are semi-prime numbers. By definition, such numbers are also classified as composite numbers.
* Primes differing by 2 are called twin primes.
Examples: 3-5, 5-7, 11-13, 17-19, 29-31, 41-43, 59-61, 71-73, 101-103, 1,000,000,009,649-1,000,000,009,651.
* The sums of all pairs of twin primes (except 3-5) are divisible by 12.
* There is only one set of triple primes - 3, 5, and 7.
* The prime number 5 is the only prime number that is both the sum and difference of two other primes.
* The primes 2 and 3 are ofter referred to as the Siamese Twins as they are the only two adjacent prime numbers.
* Every odd number is congruent to either 1 or 3 modulo(4) meaning that every odd number minus 1 or 3 is divisible by 4.
* Every prime number is congruent to one of 1, 2, 3 or 4 modulo(5).
* There are infinitely many primes of the form N^2 + 1. If of the form N^2 + 1, it does not mean it is automatically prime. Primes of the form N^2 + 1 are either prime or the product of two primes.
* Every prime of the form 4n + 1 can be written as the sum of two squares, 5, 13, 17, 29, 37, 41, 53, etc.
* No primes of the form 4n - 1 can be written as the sum of two squares, 3, 7, 11, 43, 47, 59, 67, etc.
* The number 17 is the only prime that is equal to the sum of the digits of its cube.
* A prime p is the sum of two squares if, and only if, p + 1 is not divisible by 4.
Finding Primes
The Sieve of Eratosthenes
Lets find the primes between 1 and 100.
Write down the sequence of numbers from 1 to 100.
Cross out the 1.
Beginning with the 2, strike out every second number beyond the 2, i.e., 4, 6, 8, 10, etc.
Starting from the first remaining number, 3, cross out every third number beyond the 3, i.e., 3, 6, 9, 12, etc.
Starting from the first remaining number, 5, cross out every fifth number beyond the 5, i.e., 5, 10, 15, 20, etc.
Continue with the 7, crossing out every seventh number beyond the 7, i.e., 7, 14, 21, 28, etc.
Continue the process until you have reached N or 100.
The numbers remaining are the primes between 1 and 100, namely 2, 3, 5, 7, 11, 13,17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, and 97. By definition, all the others are composite numbers.
The Sieve of Sundaram
Given the infinite table of p rows and q columns.
.4....7....10...13...16...19...22...25....28....52...57...etc.. constant 3 difference
.7...12...17...22...27...32...37...42....47....52...57...etc constant 5 difference
10..17...24...31...38...45...52...59....66....73...80...etc. constant 7 difference
13..22...31...40...49...58...67...76....85....94..103..etc. constant 9 difference
16..27...38...49...60...71...82...93...104..115..126..etc. constant 11 difference
19..32...45...58...71...84...97..110..123..136..149..etc constant 13 difference
Required to determine if the number N is prime or composite.
Let k = (N - 1)/2
If the value of k is found in the table, N is composite.
If the value of k is not found in the table, N is prime.
The 1st number in the pth row is given by 3p + 1
The successive difference in each row is given by 2q + 1
The qth number in the pth row is there defined as (2q + 1)p + q
Therefore, if values of p and q can be found to make (2q + 1)p + q = k, N is not a prime.
Hello, bware!
Pay no attention to the man behind the curtain . . .
First write all the whole number from 1 to 100:
\(\displaystyle \begin{array}{ccccccc}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 &10\\ 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20\\ 21 & 21 & 23 & 24 & 25 & 26 & 27 & 28 & 29 & 30\\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\ \\91 & 92 & 93 & 94 & 95 & 96 & 97 & 98 & 99 & 100\end{array}\)
In the following, we will be using prime nunbers: 2, 3, 5, 7, 11, 13, . . .
Keep the second number, then cross out every second number:
\(\displaystyle \begin{array}{ccccccc}1 & 2 & 3 & \not{4} & 5 & \not{6} & 7 & \not{8} & 9 & \not{10}\\ 11 & \not{12} & 13 & \not{14} & 15 & \not{16} & 17 & \not{18} & 19 & \not{20}\\ 21 & \not{22} & 23 & \not{24} & 25 & \not{26} & 27 & \not{28} & 29 & \not{30}\\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\ \\91 & \not{92} & 93 & \not{94} & 95 & \not{96} & 97 & \not{98} & 99 & \not{100}\end{array}\)
Keep the third number, then cross out every third number:
\(\displaystyle \begin{array}{ccccccc}1 & 2 & 3 & * & 5 & \not{6} & 7 & * & \not{9} & * \\ 11 & \not{12} & 13 & * & \not{15} & * & 17 & \not{18} & 19 & * \\ \not{21} & * & 23 & \not{24} & 25 & * & \not{27} & * & 29 & \not{30}\\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\ \\91 & * & \not{93} & * & 95 & \not{96} & 97 & * & \not{99} & * \end{array}\)
Keep the fifth number, then cross out every fifth number:
\(\displaystyle \begin{array}{ccccccc}1 & 2 & 3 & * & 5 & * & 7 & * & * & * \\ 11 & * & 13 & * & \not{15} & * & 17 & * & 19 & * \\ * & * & 23 & * & \not{25} & * & * & * & 29 & * \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\ \\91 & * & * & * & \not{95} & * & 97 & * & * & * \end{array}\)
Continue in this manner for all primes less than 100.
\(\displaystyle \;\;\)(Actually, you can stop after 47.)
The remaining numbers (with the exception of the leading "1") are primes.
Pay no attention to the man behind the curtain . . .
First write all the whole number from 1 to 100:
\(\displaystyle \begin{array}{ccccccc}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 &10\\ 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20\\ 21 & 21 & 23 & 24 & 25 & 26 & 27 & 28 & 29 & 30\\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\ \\91 & 92 & 93 & 94 & 95 & 96 & 97 & 98 & 99 & 100\end{array}\)
In the following, we will be using prime nunbers: 2, 3, 5, 7, 11, 13, . . .
Keep the second number, then cross out every second number:
\(\displaystyle \begin{array}{ccccccc}1 & 2 & 3 & \not{4} & 5 & \not{6} & 7 & \not{8} & 9 & \not{10}\\ 11 & \not{12} & 13 & \not{14} & 15 & \not{16} & 17 & \not{18} & 19 & \not{20}\\ 21 & \not{22} & 23 & \not{24} & 25 & \not{26} & 27 & \not{28} & 29 & \not{30}\\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\ \\91 & \not{92} & 93 & \not{94} & 95 & \not{96} & 97 & \not{98} & 99 & \not{100}\end{array}\)
Keep the third number, then cross out every third number:
\(\displaystyle \begin{array}{ccccccc}1 & 2 & 3 & * & 5 & \not{6} & 7 & * & \not{9} & * \\ 11 & \not{12} & 13 & * & \not{15} & * & 17 & \not{18} & 19 & * \\ \not{21} & * & 23 & \not{24} & 25 & * & \not{27} & * & 29 & \not{30}\\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\ \\91 & * & \not{93} & * & 95 & \not{96} & 97 & * & \not{99} & * \end{array}\)
Keep the fifth number, then cross out every fifth number:
\(\displaystyle \begin{array}{ccccccc}1 & 2 & 3 & * & 5 & * & 7 & * & * & * \\ 11 & * & 13 & * & \not{15} & * & 17 & * & 19 & * \\ * & * & 23 & * & \not{25} & * & * & * & 29 & * \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\ \\91 & * & * & * & \not{95} & * & 97 & * & * & * \end{array}\)
Continue in this manner for all primes less than 100.
\(\displaystyle \;\;\)(Actually, you can stop after 47.)
The remaining numbers (with the exception of the leading "1") are primes.
Hmmm...not 100% efficient Soroban; like many are crossed out twice!
"Keep the third number, then cross out every third number:"
Please change to:
Keep the third number, then cross out every third number not already crossed out. :idea:
Then, why list the evens > 2 when we already know them's not primes? :roll:
The "Sieve of Denis" initial list < 100:
2 3 5 7 9 11 ...... 97 99
keep 2
keep 3
cross out every 3rd number following 3
keep 5
cross out every 5th number following 5 if not already crossed out!
keepa goin'
"Keep the third number, then cross out every third number:"
Please change to:
Keep the third number, then cross out every third number not already crossed out. :idea:
Then, why list the evens > 2 when we already know them's not primes? :roll:
The "Sieve of Denis" initial list < 100:
2 3 5 7 9 11 ...... 97 99
keep 2
keep 3
cross out every 3rd number following 3
keep 5
cross out every 5th number following 5 if not already crossed out!
keepa goin'
- Joined
- Feb 4, 2004
- Messages
- 16,583
I don't think the Sieve is meant to be" the most efficient" method. It's more of a "mindless but certain" method.Denis said:
The point of the Sieve is that you don't have to do all that division and primality-checking and list-revision as you go; you can just find a prime (which will always be the next un-crossed-out number, counting from the beginning), and then cross out all of its multiples.
You ignore "1". The "next" number is "2"; circle that, and cross out every second number from there. The "next" un-crossed-out number is "3"; circle that, and cross out every third number from there. And so forth.
So the "crossing out every [x] numbers" counting process still works.Denis said:
Eliz.