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

ਵਿਕੀਪੀਡੀਆ, ਇੱਕ ਅਜ਼ਾਦ ਗਿਆਨਕੋਸ਼ ਤੋਂ

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

ਐਲਗੋਰਿਦਮ[ਸੋਧੋ]

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

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

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

ਸ਼ੁੱਧਤਾ[ਸੋਧੋ]

ਅਗਰ ਅਸੀਂ ਪੂਰਨ ਅੰਕਾਂ ਨਾਲ ਸ਼ੁਰੂ ਕਰੀਏ 1 ਤੋਂ 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;
}

ਹਵਾਲੇ[ਸੋਧੋ]

  1. V. Ramaswami Aiyar (1934). "Sundaram's Sieve for Prime Numbers". The Mathematics Student. 2 (2): 73. ISSN 0025-5742.
  2. G. (1941). "Curiosa 81. A New Sieve for Prime Numbers". Scripta Mathematica. 8 (3): 164.