सीव ऑफ़ सुंदरम

गणित में सीव ऑफ़ सुंदरम एक निर्दिष्ट पूर्णांक तक सभी अभाज्य संख्याओं को खोजने के लिए एक सरल निर्धारक एल्गोरिथम है। इसकी खोज भारतीय गणितज्ञ एसपी सुंदरम ने 1934 में की थी। उन्हीं के ऊपर इसका नाम पड़ा।

कलन विधि

सुंदरम की छलनी: 202 से नीचे के अपराधों के लिए एल्गोरिदम चरण (अडॉप्टिमाइज्ड)।

एल्गोरिथ्म 1 से लेकर $N$ तक की प्राकृतिक संख्याओं में $i+j+2ij$ रूप की संख्याओं को अलग करने का प्रावधान करता है; जहाँ $i\leqslant j$  और $i+j+2ij\leqslant N$ शर्तें मान्य हैं;

और

$i=1,\;2,\;\ldots ,\;\left\lfloor {\frac {{\sqrt {2N+1}}-1}{2}}\right\rfloor$

और

$j=i,\;i+1,\;\ldots ,\;\left\lfloor {\frac {N-i}{2i+1}}\right\rfloor .$

शुद्धता

यह एल्गोरिथ्म एक से बड़े विषम धनात्मक पूर्णांकों (odd positive integers) के साथ काम करता है, जो कि $2m+1$ रूप में हों, जहाँ $m$ एक प्राकृतिक संख्या है।

यदि $2m+1$ समग्र संख्या (composite number) है , इसे एक से अधिक दो विषम संख्याओं के उत्पाद के रूप में दर्शाया जाता है, जो है:

$2m+1=(2i+1)(2j+1)$,

जहाँ $i$ और $j$ प्राकृतिक संख्याएँ हैं। अनुपात को नीचे जैसा दिया गया है, उस तरह भी समझा जा सकता है:

$m=2ij+i+j$।

अतः, यदि हम $2ij+i+j$ (जहाँ $1\leqslant i\leqslant j$) रूप की सभी  संख्याओं को हटा दें, तो प्रत्येक $m$ के लिए $2m+1$ संख्या सरल (simple, non-composite number) होना चाहिए।

इसके विपरीत, यदि संख्या $2m+1$ अभाज्य (prime number) है तो संख्या $m$ को $2ij+i+j$ के रूप में लिखना असंभव है। इस प्रकार एल्गोरिथ्म के संचालन के दौरान $m$ बाहर नहीं छूटेगा।

C में प्रोग्राम

#include <stdio.h>
int main(void) {
    int i,j,n;
    scanf("%d",&n);
    char a[n];
    
    for (i=1; i<=n; i++)
        a[i]=1;

    for(i=1;2*i*(i+1)<n;i++)
        for(j=i;j<=(n-i)/(2*i+1);j++)
            a[2*i*j+i+j]=0;
    
    for(i=0;i<n;i++)
        if(a[i])
            printf("%d ",2*i+1);
    return 0;
}

यह सभी देखें

• एराटोस्थनीज की छलनी
• Atkin की चलनी
• चलनी सिद्धांत

संदर्भ

• Ogilvy, C. Stanley; John T. Anderson (1988). Excursions in Number Theory. Dover Publications, 1988 (reprint from ऑक्सफोर्ड यूनिवर्सिटी प्रेस, 1966). पपृ॰ 98–100, 158. आई॰ऍस॰बी॰ऍन॰ 0-486-25778-9. Ogilvy, C. Stanley; John T. Anderson (1988). Excursions in Number Theory. Dover Publications, 1988 (reprint from ऑक्सफोर्ड यूनिवर्सिटी प्रेस, 1966). पपृ॰ 98–100, 158. आई॰ऍस॰बी॰ऍन॰ 0-486-25778-9. Ogilvy, C. Stanley; John T. Anderson (1988). Excursions in Number Theory. Dover Publications, 1988 (reprint from ऑक्सफोर्ड यूनिवर्सिटी प्रेस, 1966). पपृ॰ 98–100, 158. आई॰ऍस॰बी॰ऍन॰ 0-486-25778-9.
• Honsberger, Ross (1970). Ingenuity in Mathematics. New Mathematical Library #23. Mathematical Association of America. पपृ॰ 75. आई॰ऍस॰बी॰ऍन॰ 0-394-70923-3. Honsberger, Ross (1970). Ingenuity in Mathematics. New Mathematical Library #23. Mathematical Association of America. पपृ॰ 75. आई॰ऍस॰बी॰ऍन॰ 0-394-70923-3. Honsberger, Ross (1970). Ingenuity in Mathematics. New Mathematical Library #23. Mathematical Association of America. पपृ॰ 75. आई॰ऍस॰बी॰ऍन॰ 0-394-70923-3.
• अपराधों के लिए एक नई "चलनी" , Kordemski, Boris A. (1974). Köpfchen, Köpfchen! Mathematik zur Unterhaltung. MSB Nr. 78. Urania Verlag. पृ॰ 200. एक अंश Kordemski, Boris A. (1974). Köpfchen, Köpfchen! Mathematik zur Unterhaltung. MSB Nr. 78. Urania Verlag. पृ॰ 200. Kordemski, Boris A. (1974). Köpfchen, Köpfchen! Mathematik zur Unterhaltung. MSB Nr. 78. Urania Verlag. पृ॰ 200. Kordemski, Boris A. (1974). Köpfchen, Köpfchen! Mathematik zur Unterhaltung. MSB Nr. 78. Urania Verlag. पृ॰ 200. Kordemski, Boris A. (1974). Köpfchen, Köpfchen! Mathematik zur Unterhaltung. MSB Nr. 78. Urania Verlag. पृ॰ 200. Kordemski, Boris A. (1974). Köpfchen, Köpfchen! Mathematik zur Unterhaltung. MSB Nr. 78. Urania Verlag. पृ॰ 200. (रूसी पुस्तक Кордемский, Борис Анастасьевич (1958). Математическая смекалка. М.: ГИФМЛ. मूल से 16 अक्तूबर 2019 को पुरालेखित. अभिगमन तिथि 16 अक्तूबर 2019. Кордемский, Борис Анастасьевич (1958). Математическая смекалка. М.: ГИФМЛ. मूल से 16 अक्तूबर 2019 को पुरालेखित. अभिगमन तिथि 16 अक्तूबर 2019. Кордемский, Борис Анастасьевич (1958). Математическая смекалка. М.: ГИФМЛ. मूल से 16 अक्तूबर 2019 को पुरालेखित. अभिगमन तिथि 16 अक्तूबर 2019. )
• Movshovitz-Hadar, N. (1988). "Stimulating Presentations of Theorems Followed by Responsive Proofs". For the Learning of Mathematics. 8 (2): 12–19.
• (Thesis). 
• Baxter, Andrew. "Sundaram's Sieve". Topics from the History of Cryptography. MU Department of Mathematics. मूल से 12 अगस्त 2011 को पुरालेखित. अभिगमन तिथि 16 अक्तूबर 2019.

बाहरी कड़ियाँ

• बिटारेज़ का उपयोग करके सुंदरम की छलनी का एक C99 कार्यान्वयन