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

गणित में सीव ऑफ़ सुंदरम एक निर्दिष्ट पूर्णांक तक सभी अभाज्य संख्याओं को खोजने के लिए एक सरल निर्धारक एल्गोरिथम है। इसकी खोज भारतीय गणितज्ञ एसपी सुंदरम ने 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 की चलनी
• चलनी सिद्धांत

संदर्भ

• साँचा:Cite book साँचा:Cite book साँचा:Cite book
• साँचा:Cite book साँचा:Cite book साँचा:Cite book
• अपराधों के लिए एक नई "चलनी" साँचा:Dead link , साँचा:Cite book एक अंश साँचा:Cite book साँचा:Cite book साँचा:Cite book साँचा:Cite book साँचा:Cite book (रूसी पुस्तक साँचा:Cite book साँचा:Cite book साँचा:Cite book )
• साँचा:Cite journal
• साँचा:Cite thesis
• साँचा:Cite journal

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

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