Difference between revisions of "Sieve of Sundaram"
(Created page with "==Description== The '''Sieve of Sundaram''' is a sieve for a range of '''odd''' prime numbers.The sieve starts out listing the natural numbers <math>1</math>...") |
m (→Optimization) |
||
| Line 71: | Line 71: | ||
==Optimization== | ==Optimization== | ||
| − | + | The equivalent in Step 2 above, of the [[Sieve of Eratosthenes]] starting the at the next prime squared, is starting at <math>2c^2+2c</math> for next index <math>c</math> | |
==Generalization== | ==Generalization== | ||
Looking close, if you know [[modular arithmetic]], you'll note the remainder 1 forms the modular multiplicative group modulo 2. This generalizes to the modular multiplicative group mod any natural number. | Looking close, if you know [[modular arithmetic]], you'll note the remainder 1 forms the modular multiplicative group modulo 2. This generalizes to the modular multiplicative group mod any natural number. | ||
Revision as of 09:24, 27 February 2020
Description
The Sieve of Sundaram is a sieve for a range of odd prime numbers.The sieve starts out listing the natural numbers 
to 
like the following example (
)
![\[\begin{array}{ccccccccccccccc} 1&2&3&4&5&6&7&8&9&10&11&12&13&14&15\\ 16&17&18&19&20&21&22&23&24&25&26&27&28&29&30\\ 31&32&33&34&35&36&37&38&39&40&41&42&43&44&45\\ 46&47&48&49&50&51&52&53&54&55&56&57&58&59&60\\ 61&62&63&64&65&66&67&68&69&70&71&72&73&74&75\\ 76&77&78&79&80&81&82&83&84&85&86&87&88&89&90\\ 91&92&93&94&95&96&97&98&99&100&101&102&103&104&105\\ 106&107&108&109&110&111&112&113&114&115&116&117&118&119&120\\ 121&122&123&124&125&126&127&128&129&130&131&132&133&134&135\\ 136&137&138&139&140&141&142&143&144&145&146&147&148&149&150\\ 151&152&153&154&155&156&157&158&159&160&161&162&163&164&165\\ 166&167&168&169&170&171&172&173&174&175&176&177&178&179&180\\ 181&182&183&184&185&186&187&188&189&190&191&192&193&194&195\\ 196&197&198&199&200&201&202&203&204&205&206&207&208&209&210\\ 211&212&213&214&215&216&217&218&219&220&231&222&223&224&225\\ 226&227&228&229&230&231&232&233&234&235&236&237&238&239&240\\ \end{array}\]](http://latex.artofproblemsolving.com/1/f/b/1fb43c28342ee1eef193f9405ef6ba6e6df9d701.png)
Step 2
Then it finds all numbers of form 
( fancy way of saying start at 
and increase by 
, for each not already eliminated ) and eliminates them (empty cells):
![\[\begin{array}{ccccccccccccccc} 1&2&3&&5&6&&8&9&&11&&&14&15\\ &&18&&20&21&&23&&&26&&&29&30\\ &&33&&35&36&&&39&&41&&&44&\\ &&48&&50&51&&53&54&&56&&&&\\ &&63&&65&&&68&69&&&&&74&75\\ &&78&&&81&&83&&&86&&&89&90\\ &&&&95&96&&98&99&&&&&&105\\ &&&&&111&&113&114&&116&&&119&120\\ &&&&125&&&128&&&131&&&134&135\\ &&138&&140&141&&&&&146&&&&\\ &&153&&155&156&&158&&&&&&&165\\ &&168&&&&&173&174&&176&&&179&\\ &&183&&&186&&&189&&191&&&194&\\ &&198&&200&&&&204&&&&&209&210\\ &&&&215&216&&&219&&221&&&224&\\ &&228&&230&231&&233&&&&&&239&\\ \end{array}\]](http://latex.artofproblemsolving.com/8/b/9/8b96884dfae94b90bdead212feac47cfb43f5df6.png)
Step 3
Double each number and add one:
![\[\begin{array}{ccccccccccccccc} 3&5&7&&11&13&&17&19&&23&&&29&31\\ &&37&&41&43&&47&&&53&&&59&61\\ &&67&&71&73&&&79&&83&&&89&\\ &&97&&101&103&&107&109&&113&&&&\\ &&127&&131&&&137&139&&&&&149&151\\ &&157&&&163&&167&&&173&&&179&181\\ &&&&191&193&&197&199&&&&&&211\\ &&&&&223&&227&229&&233&&&239&241\\ &&&&251&&&257&&&263&&&269&271\\ &&277&&281&283&&&&&293&&&&\\ &&307&&311&313&&317&&&&&&&331\\ &&337&&&&&347&349&&353&&&359&\\ &&367&&&373&&&379&&383&&&389&\\ &&397&&401&&&&409&&&&&419&421\\ &&&&431&433&&&439&&443&&&449&\\ &&457&&461&463&&467&&&&&&479&\\ \end{array}\]](http://latex.artofproblemsolving.com/0/e/8/0e89acc7a18058912a639f17412b9eec35f004e2.png)
Optimization
The equivalent in Step 2 above, of the Sieve of Eratosthenes starting the at the next prime squared, is starting at 
for next index 
Generalization
Looking close, if you know modular arithmetic, you'll note the remainder 1 forms the modular multiplicative group modulo 2. This generalizes to the modular multiplicative group mod any natural number.
