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

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

ਐਲਗੋਰਿਦਮ

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

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

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

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

ਸ਼ੁੱਧਤਾ

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

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

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

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

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

ਹਵਾਲੇ

• Ogilvy, C. Stanley; John T. Anderson (1988). Excursions in Number Theory. Dover Publications, 1988 (reprint from Oxford University Press, 1966). pp. 98–100, 158. ISBN 0-486-25778-9. Ogilvy, C. Stanley; John T. Anderson (1988). Excursions in Number Theory. Dover Publications, 1988 (reprint from Oxford University Press, 1966). pp. 98–100, 158. ISBN 0-486-25778-9. Ogilvy, C. Stanley; John T. Anderson (1988). Excursions in Number Theory. Dover Publications, 1988 (reprint from Oxford University Press, 1966). pp. 98–100, 158. ISBN 0-486-25778-9.
• Honsberger, Ross (1970). Ingenuity in Mathematics. New Mathematical Library #23. Mathematical Association of America. pp. 75. ISBN 0-394-70923-3. Honsberger, Ross (1970). Ingenuity in Mathematics. New Mathematical Library #23. Mathematical Association of America. pp. 75. ISBN 0-394-70923-3. Honsberger, Ross (1970). Ingenuity in Mathematics. New Mathematical Library #23. Mathematical Association of America. pp. 75. ISBN 0-394-70923-3.
• ਪ੍ਰਾਈਮਜ਼ ਲਈ ਇੱਕ ਨਵਾਂ "ਸਿਈਵੀ"  , Kordemski, Boris A. (1974). Köpfchen, Köpfchen! Mathematik zur Unterhaltung. MSB Nr. 78. Urania Verlag. p. 200. ਇੱਕ ਅੰਸ਼ Kordemski, Boris A. (1974). Köpfchen, Köpfchen! Mathematik zur Unterhaltung. MSB Nr. 78. Urania Verlag. p. 200. Kordemski, Boris A. (1974). Köpfchen, Köpfchen! Mathematik zur Unterhaltung. MSB Nr. 78. Urania Verlag. p. 200. Kordemski, Boris A. (1974). Köpfchen, Köpfchen! Mathematik zur Unterhaltung. MSB Nr. 78. Urania Verlag. p. 200. Kordemski, Boris A. (1974). Köpfchen, Köpfchen! Mathematik zur Unterhaltung. MSB Nr. 78. Urania Verlag. p. 200. Kordemski, Boris A. (1974). Köpfchen, Köpfchen! Mathematik zur Unterhaltung. MSB Nr. 78. Urania Verlag. p. 200. (ਰੂਸੀ ਕਿਤਾਬ ਦਾ ਅਨੁਵਾਦ Кордемский, Борис Анастасьевич (1958). Математическая смекалка. М.: ГИФМЛ. Archived from the original on 2019-10-16. Retrieved 2019-10-29. {{cite book}}: Unknown parameter |dead-url= ignored (|url-status= suggested) (help) Кордемский, Борис Анастасьевич (1958). Математическая смекалка. М.: ГИФМЛ. Archived from the original on 2019-10-16. Retrieved 2019-10-29. {{cite book}}: Unknown parameter |dead-url= ignored (|url-status= suggested) (help) Кордемский, Борис Анастасьевич (1958). Математическая смекалка. М.: ГИФМЛ. Archived from the original on 2019-10-16. Retrieved 2019-10-29. {{cite book}}: Unknown parameter |dead-url= ignored (|url-status= suggested) (help))
• Movshovitz-Hadar, N. (1988). "Stimulating Presentations of Theorems Followed by Responsive Proofs". For the Learning of Mathematics. 8 (2): 12–19.
• Ferrando, Elisabetta (2005). ਅਨੁਮਾਨ ਲਗਾਉਣ ਅਤੇ ਸਾਬਤ ਕਰਨ ਵਿੱਚ ਅਗਵਾ ਕਰਨ ਵਾਲੀਆਂ ਪ੍ਰਕਿਰਿਆਵਾਂ (ਪੀਡੀਐਫ) (ਪੀਐਚਡੀ). ਪਰਡਯੂ ਯੂਨੀਵਰਸਿਟੀ. ਪੀਪੀ.   70-72.
• Baxter, Andrew. "Sundaram's Sieve". Topics from the History of Cryptography. MU Department of Mathematics. Archived from the original on 2011-08-12. Retrieved 2019-10-29. {{cite journal}}: Unknown parameter |dead-url= ignored (|url-status= suggested) (help)