deecarney4 said:
Does anyone understand this Sieve of Eratosthenes
Example: find all prime numbers of 100
Largest prime number needed to check to solve the problem
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.