ਸੁੰਦਰਮ ਦੀ ਛਾਣਨੀ

ਗਣਿਤ ਵਿੱਚ, ਸੁੰਦਰਮ ਦੀ ਛਾਣਨੀ (Sieve of Sundaram) ਇੱਕ ਨਿਸ਼ਚਤ ਪੂਰਨ ਅੰਕ ਤੱਕ ਸਾਰੇ ਅਭਾਜ ਅੰਕਾਂ ਨੂੰ ਲੱਭਣ ਲਈ ਇੱਕ ਸਧਾਰਨ ਨਿਰਣਾਤਮਕ ਕਲਨਵਿਧੀ (ਐਲਗੋਰਿਦਮ) ਹੈ। ਇਸਦੀ ਖੋਜ ਭਾਰਤੀ ਗਣਿਤ ਸ਼ਾਸਤਰੀ ਐਸ ਪੀ ਸੁੰਦਰਮ ਨੇ 1934 ਵਿੱਚ ਕੀਤੀ ਸੀ। ਇਹ ਸੁੰਦਰਮ ਦੀ ਛਾਣਨੀ ਉਸਦੇ ਨਾਮ ਤੇ ਰੱਖਿਆ ਗਿਆ ਸੀ।

 ਐਲਗੋਰਿਦਮ 
ਪੂਰਨ ਅੰਕਾਂ ਦੀ ਸੂਚੀ 1 ਤੋਂ n ਤੱਕ ਨਾਲ ਸ਼ੁਰੂ ਕਰੋ। ਇਸ ਸੂਚੀ ਵਿਚੋਂ,  ਰੂਪ ਦੇ ਸਾਰੇ ਨੰਬਰ ਹਟਾਓ ਜਿੱਥੇ:




ਬਾਕੀ ਨੰਬਰਾਂ ਨੂੰ ਇੱਕ ਇੱਕ ਕਰਕੇ ਦੁਗਣਾ ਕੀਤਾ ਜਾਂਦਾ ਹੈ ਅਤੇ ਇੱਕ ਜੋੜ ਦਿੱਤਾ ਜਾਂਦਾ ਹੈ, ਜਿਸ ਨਾਲ  ਟਾਂਕ  ਅਭਾਜ ਸੰਖਿਆਵਾਂ (ਅਰਥਾਤ, 2 ਨੂੰ ਛੱਡ ਕੇ ਸਾਰੀਆਂ ਅਭਾਜ ਸੰਖਿਆਵਾਂ ਦੀ) 2n + 2 ਤੋਂ ਹੇਠਾਂ ਦੀ ਇੱਕ ਸੂਚੀ ਮਿਲ ਜਾਂਦੀ ਹੈ।

 ਸ਼ੁੱਧਤਾ 
ਅਗਰ ਅਸੀਂ ਪੂਰਨ ਅੰਕਾਂ ਨਾਲ ਸ਼ੁਰੂ ਕਰੀਏ  ਤੋਂ n ਤੱਕ, ਅੰਤਮ ਸੂਚੀ ਵਿੱਚ ਸਿਰਫ 3 ਤੋਂ  ਟਾਂਕ ਪੂਰਨ ਅੰਕ ਹੋਣਗੇ। ਇਸ ਅੰਤਮ ਸੂਚੀ ਵਿਚੋਂ, ਕੁਝ ਟਾਂਕ ਪੂਰਨ ਅੰਕਾਂ ਨੂੰ ਬਾਹਰ ਰੱਖਿਆ ਗਿਆ ਹੈ; ਸਾਨੂੰ ਇਹ ਦਰਸਾਉਣਾ ਚਾਹੀਦਾ ਹੈ ਕਿ ਇਹ ਬਿਲਕੁਲ  ਨਾਲੋਂ ਘੱਟ ਕੰਪੋਜ਼ਿਟ  ਟਾਂਕ ਪੂਰਨ ਅੰਕ ਹਨ।

ਮੰਨ ਲਓ q  ਰੂਪ ਦਾ ਇੱਕ ਟਾਂਕ ਪੂਰਨ ਅੰਕ ਹੈ। ਤਾਂ, q ਸਿਰਫ ਅਤੇ ਸਿਰਫ ਜੇ ਉਸ ਹਾਲਤ ਵਿੱਚ ਬਾਹਰ ਰੱਖਿਆ ਜਾਵੇਗਾ ਜੇ k , ਯਾਨੀ  ਰੂਪ ਦਾ ਹੈ। ਫਿਰ ਸਾਡੇ ਕੋਲ ਆ ਜਾਂਦੇ ਹਨ:



ਇਸ ਲਈ, ਇੱਕ ਟਾਂਕ ਪੂਰਨ ਅੰਕ ਨੂੰ ਅੰਤਮ ਸੂਚੀ ਵਿਚੋਂ ਬਾਹਰ ਕੱਢ ਦਿੱਤਾ ਜਾਂਦਾ ਹੈ ਜੇ ਅਤੇ ਕੇਵਲ ਜੇ ਇਸ ਵਿੱਚ  ਦੇ ਰੂਪ ਵਿੱਚ ਇੱਕ ਗੁਣਨ ਖੰਡ ਹੈ - ਜਿਸ ਦਾ ਭਾਵ ਹੈ ਕਿ, ਜੇ ਇਸ ਵਿੱਚ ਇੱਕ ਗੈਰ- ਮਾਮੂਲੀ ਟਾਂਕ ਗੁਣਨ ਖੰਡ ਹੈ। ਇਸ ਲਈ ਸੂਚੀ ਐਨ ਸਹੀ ਸਹੀ  ਤੋਂ ਘੱਟ ਜਾਂ ਇਸ ਦੇ ਬਰਾਬਰ ਦੀਆਂ ਟਾਂਕ  ਅਭਾਜ  ਸੰਖਿਆਵਾਂ ਦੇ ਸਮੂਹ ਦੀ ਬਣੀ ਹੋਵੇਗੀ।

 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;
}

 ਹਵਾਲੇ 



 ਪ੍ਰਾਈਮਜ਼ ਲਈ ਇੱਕ ਨਵਾਂ "ਸਿਈਵੀ"  ,  ਇੱਕ ਅੰਸ਼      (ਰੂਸੀ ਕਿਤਾਬ ਦਾ ਅਨੁਵਾਦ   ) 

 Ferrando, Elisabetta (2005). ਅਨੁਮਾਨ ਲਗਾਉਣ ਅਤੇ ਸਾਬਤ ਕਰਨ ਵਿੱਚ ਅਗਵਾ ਕਰਨ ਵਾਲੀਆਂ ਪ੍ਰਕਿਰਿਆਵਾਂ (ਪੀਡੀਐਫ) (ਪੀਐਚਡੀ). ਪਰਡਯੂ ਯੂਨੀਵਰਸਿਟੀ. ਪੀਪੀ.   70-72.