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

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

ਐਲਗੋਰਿਦਮ

ਸੁੰਦਰਮ ਦੀ ਸਿਈਵੀ: 202 ਤੋਂ ਘੱਟ ਪ੍ਰਾਈਮਜ਼ (ਗੈਰ-ਬਿਨ੍ਹਾਂ) ਲਈ ਐਲਗੋਰਿਦਮ ਕਦਮ.

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

• $i,j\in \mathbb{N},1\le i\le j$
• $i+j+2ij\le n$

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

ਸ਼ੁੱਧਤਾ

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

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

$\begin{array}{cc}q& =2(i+j+2ij)+1\\ & =2i+2j+4ij+1\\ & =(2i+1)(2j+1).\end{array}$

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

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

ਹਵਾਲੇ

• ਫਰਮਾ:Cite book ਫਰਮਾ:Cite book ਫਰਮਾ:Cite book
• ਫਰਮਾ:Cite book ਫਰਮਾ:Cite book ਫਰਮਾ:Cite book
• ਪ੍ਰਾਈਮਜ਼ ਲਈ ਇੱਕ ਨਵਾਂ "ਸਿਈਵੀ"ਫਰਮਾ:ਮੁਰਦਾ ਕੜੀ  , ਫਰਮਾ:Cite book ਇੱਕ ਅੰਸ਼ ਫਰਮਾ:Cite book ਫਰਮਾ:Cite book ਫਰਮਾ:Cite book ਫਰਮਾ:Cite book ਫਰਮਾ:Cite book (ਰੂਸੀ ਕਿਤਾਬ ਦਾ ਅਨੁਵਾਦ ਫਰਮਾ:Cite book ਫਰਮਾ:Cite book ਫਰਮਾ:Cite book)
• ਫਰਮਾ:Cite journal
• Ferrando, Elisabetta (2005). ਅਨੁਮਾਨ ਲਗਾਉਣ ਅਤੇ ਸਾਬਤ ਕਰਨ ਵਿੱਚ ਅਗਵਾ ਕਰਨ ਵਾਲੀਆਂ ਪ੍ਰਕਿਰਿਆਵਾਂ (ਪੀਡੀਐਫ) (ਪੀਐਚਡੀ). ਪਰਡਯੂ ਯੂਨੀਵਰਸਿਟੀ. ਪੀਪੀ.   70-72.
• ਫਰਮਾ:Cite journal