View source for Sieve of Sundaram

==Description==

The '''Sieve of Sundaram''' is a sieve for a range of '''odd''' [[prime number|prime numbers]].The sieve starts out listing the natural numbers <math>1</math> to <math>n</math> like the following example (<math>n=240</math>)

<cmath>\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}</cmath>

===Step 2===

Then it finds all numbers of form <math>2ab+a+b</math> ( fancy way of saying start at <math>a</math> and increase by <math>2a+1</math>, for each not already eliminated <math>a</math>) and eliminates them (empty cells):

<cmath>\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}</cmath>


===Step 3===

Double each number and add one:

<cmath>\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}</cmath>

==Basis==

The basis of the algorithm is that for <math>1\leq a\leq b</math> (without loss of generality, as the form we double and add 1 to is made up of commutative operations); <math>2(2ab+a+b)+1=(2a+1)(2b+1)</math> with both factors nontrivial. 

==Optimization==

The equivalent in Step 2 above, of the [[Sieve of Eratosthenes]] starting the at the next prime squared, is starting at <math>2f^2+2f</math> for next index <math>f</math>

==Generalization for prime finding==

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( with loss of factors in the prime list). This generalization either needs <math>\varphi(m)</math> copies of the same numbers ( one for each class), or <math>T_{\varphi(m)}</math> (triangle numbers) colors  . The class of remainder 1, is the only class where variable must stay nonzero to introduce a nontrivial factor by default ( negative representatives increase variable value required by 1). Modulo 30 is sketched out below (8 classes):

<cmath>\begin{array}{ccccccccc}
c\slash d&1&7&11&13&17&19&23&29\\
1&a+b&7a+b&11a+b&13a+b&17a+b&19a+b&23a+b&29a+b\\
7&a+7b&7(a+b)+1&11a+7b+2&13a+7b+3&17a+7b+3&19a+7+4&23a+7b+5&29a+7b+6\\
11&a+11b&7a+11b+2&11(a+b)+4&13a+11b+4&17a+11b+6&19a+11b+6&23a+11b+8&29a+11b+10\\
13&a+13b&7a+13b+3&11a+13b+4&13(a+b)+5&17a+13b+7&19a+13b+8&23a+13b+9&29a+13b+12\\
17&a+17b&7a+17b+3&11a+17b+6&13a+17b+7&17(a+b)+9&19a+17b+10&23a+17b+13&29a+17b+16\\
19&a+19b&7a+19b+4&11a+19b+6&13a+19b+8&17a+19b+10&19(a+b)+12&23a+19b+14&29a+19b+18\\
23&a+23b&7a+23b+13&11a+23b+8&13a+23b+9&17a+23b+13&19a+23a+14&23(a+b)+17&29a+23b+22\\
29&a+29b&7a+29b+6&11a+29b+10&13a+29b+12&17a+29b+16&19a+29b+18&23a+29b+22&29(a+b)+28\\
\end{array}</cmath>

The table leaves <math>30ab</math> off each to save space. the general rule, for modulus <math>m</math>, with remainders <math>c,d</math> is: <cmath>m(mab+da+cb+\lfloor {cd\over m}\rfloor)+(cd\bmod m)</cmath> in general.

==Generalization for r-almost prime finding==

<math>r</math>-almost prime

: A natural number with <math>r</math> prime factors including repetitions.

The sieve can be recursed on arguments <math>a</math> and <math>b</math> to check <math>mb+d</math> or <math>ma+c</math> for primality, if both are, we have a semiprime.

On the chance we don't get back prime for more than one, we can test the components. This will find out if our original number had 3 prime factors. 

In the case of neither of <math>a,b</math> get back prime we have at least 4 prime factors, and this can go to any depth you choose. 


See Also:

[[Number Theory]]
[[Sieve of Eratosthenes]]



[[Category:Algorithms]]