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

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

कलन विधि

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

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

और

$i=1,2,\dots ,\lfloor \frac{\sqrt{2N+1}-1}{2}\rfloor$

और

$j=i,i+1,\dots ,\lfloor \frac{N-i}{2i+1}\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⩽i⩽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 Excursions in Number Theory. Dover Publications, 1988 (reprint from ऑक्सफोर्ड यूनिवर्सिटी प्रेस, 1966).ISBN 0-486-25778-9. Ogilvy, C. Stanley Excursions in Number Theory. Dover Publications, 1988 (reprint from ऑक्सफोर्ड यूनिवर्सिटी प्रेस, 1966).ISBN 0-486-25778-9. Ogilvy, C. Stanley Excursions in Number Theory. Dover Publications, 1988 (reprint from ऑक्सफोर्ड यूनिवर्सिटी प्रेस, 1966).ISBN 0-486-25778-9.
• Honsberger, Ross Ingenuity in Mathematics. Mathematical Association of America.ISBN 0-394-70923-3. Honsberger, Ross Ingenuity in Mathematics. Mathematical Association of America.ISBN 0-394-70923-3. Honsberger, Ross Ingenuity in Mathematics. Mathematical Association of America.ISBN 0-394-70923-3.
• अपराधों के लिए एक नई "चलनी" साँचा:Dead link , Kordemski, Boris A. Köpfchen, Köpfchen! Mathematik zur Unterhaltung. Urania Verlag. एक अंश Kordemski, Boris A. Köpfchen, Köpfchen! Mathematik zur Unterhaltung. Urania Verlag. Kordemski, Boris A. Köpfchen, Köpfchen! Mathematik zur Unterhaltung. Urania Verlag. Kordemski, Boris A. Köpfchen, Köpfchen! Mathematik zur Unterhaltung. Urania Verlag. Kordemski, Boris A. Köpfchen, Köpfchen! Mathematik zur Unterhaltung. Urania Verlag. Kordemski, Boris A. Köpfchen, Köpfchen! Mathematik zur Unterhaltung. Urania Verlag. (रूसी पुस्तक Кордемский, Борис Анастасьевич Математическая смекалка. М.: ГИФМЛ. Кордемский, Борис Анастасьевич Математическая смекалка. М.: ГИФМЛ. Кордемский, Борис Анастасьевич Математическая смекалка. М.: ГИФМЛ. )
• Movshovitz-Hadar, N. "Stimulating Presentations of Theorems Followed by Responsive Proofs". For the Learning of Mathematics. 8(2)

12–19.

• साँचा:Cite thesis
• Baxter, Andrew "Sundaram’s Sieve". Topics from the History of Cryptography. [१]Retrieved 16 अक्तूबर 2019.

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

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