ग्रीक गणितज्ञ इरेटॉस्थेनिझ (Eratosthenes : इ.स.पू. सुमारे 276 – 194)  यांनी  ‘P‘  या दिलेल्या एक पेक्षा मोठ्या नैसर्गिक संख्येपर्यंतच्या सर्व अविभाज्य संख्या शोधण्याची जी पद्धत सांगितली, तिला ‘इरेटॉस्थेनिझची चाळणी’ असे म्हणतात. अविभाज्य संख्या शोधण्याच्या विविध पद्धतींपैकी ही एक सोपी आणि प्रभावी पद्धत आहे.

एखादी नैसर्गिक संख्या दिली असता, ती अविभाज्य आहे किंवा नाही हे ठरविण्यासाठी सर्वांत सरळ पद्धत म्हणजे त्या संख्येपेक्षा लहान प्रत्येक नैसर्गिक संख्येने दिलेल्या संख्येला भागून त्या संख्येचे विभाजक शोधणे हा आहे. जर दिलेल्या संख्येला '1' हा एकच विभाजक असेल, तर दिलेली संख्या अविभाज्य संख्या असते. ही प्रक्रिया मोठ्या नैसर्गिक संख्यांसाठी खूपच क्लिष्ट ठरते. परंतु संयुक्त (अविभाज्य नसलेल्या 1 पेक्षा मोठ्या) संख्यांचा एक गुणधर्म ही प्रक्रिया सुलभ करण्यासाठी वापरता येतो. A ही कोणतीही संयुक्त संख्या असेल, तर ती  A = B \times C अशी लिहिता येते, जिथे 1 < B < A आणि 1 < C < A ही अट असते.

जर  B \leq C असेल, तर B^2 \leq B \times C = A  म्हणजेच B \leq \sqrt A अशी अट मिळते.

अंकगणिताच्या मूलभूत सिद्धांतानुसार B ला एकतरी अविभाज्य विभाजक P असेल. त्यामुळे A ला \sqrt A किंवा त्याहून लहान असा अविभाज्य विभाजक असतो हे निश्चित होते. त्यामुळे 1 पेक्षा मोठ्या A या नैसर्गिक संख्येची अविभाज्यता ठरवण्यासाठी \sqrt A किंवा त्याहून लहान अविभाज्य संख्यांनी A ला भागणे ही प्रक्रिया पुरेशी आहे. उदा., 509 ही संख्या अविभाज्य आहे की नाही ठरवण्यासाठी 22 पेक्षा लहान अविभाज्य संख्या 509 च्या विभाजक आहेत का ते तपासणे पुरेसे आहे (कारण 22 < \sqrt {509} < 23).

A या 1 पेक्षा मोठ्या पूर्णांकाला जर \sqrt A किंवा त्याहून लहान अविभाज्य संख्येने नि:शेष भाग जात नसेल, तर A ही अविभाज्य संख्या असते, याचाच वापर करून इरॅटोस्थेनिस  यांनी ‘इरॅटोस्थेनिसची चाळणी ही पद्धत सांगितली. या पद्धतीत जर A या 1 पेक्षा मोठ्या नैसर्गिक संख्येपर्यंतच्या अविभाज्य संख्या शोधायच्या असतील तर सर्वप्रथम 2 पासून A पर्यंतचे सर्व पूर्णांक क्रमाने लिहिले जातात. त्यानंतर त्यातून 2 पासून \sqrt A किंवा त्याहून लहान सर्व अविभाज्य संख्यांचे या अविभाज्य संख्या सोडूनचे A पर्यंतचे सर्व विभाज्य काढून टाकले जातात. यानंतर या चाळणीत उरलेल्या सर्व संख्या या अविभाज्य संख्या असतात.

उदाहरणार्थ, इरेटॉस्थेनिझच्या चाळणीद्वारे 100 पर्यंतच्या सर्व अविभाज्य संख्या शोधण्यासाठी पुढील प्रक्रिया अवलंबिली जाते :

  •  2 ते 100 पर्यंतचे सर्व पूर्णांक लिहावेत.
  •  2 ही पहिली अविभाज्य संख्या असल्याने 2 सोडून 100 पर्यंतच्या 2 च्या पटीतील सर्व संख्या काढून टाकाव्यात. त्यामुळे 4, 6, ..., 98, 100 या संख्या काढल्या जातील.
  •  त्यानंतरची पहिली काढून न टाकलेली संख्या 3 असल्याने 3 सोडून उरलेल्या संख्यांतील 3 च्या पटीतील सर्व संख्या काढून टाकाव्यात. त्यामुळे 9, 15,..., 99 या संख्याही काढल्या जातील.
  •  त्यानंतर 5 ही अविभाज्य संख्या उरली आहे. 5 सोडून 5 च्या पटीतील संख्या काढाव्यात. म्हणजे 25, 35, ..., 95 या संख्याही काढल्या जातील.
  •  हीच प्रक्रिया पुढील न काढलेली संख्या म्हणजे 7 च्या बाबतीत करावी.

\sqrt {100} (= 10) पेक्षा लहान सर्व अविभाज्य संख्यांच्या पटीतील संयुक्त संख्या चाळणीतून काढून टाकल्याने उरलेल्या 2, 3, 5, 7, 11, ...., 83, 89, 97 या संख्या 100 पेक्षा लहान असलेल्या सर्व अविभाज्य संख्या आहेत. ही संपूर्ण प्रक्रिया केल्यानंतर मिळालेली इरेटॉस्थेनिझची चाळणी खाली दर्शविली आहे :

11 21 31 41 51 61 71 81 91
2 12 22 32 42 52 62 72 82 92
3 13 23 33 43 53 63 73 83 93
4 14 24 34 44 54 64 74 84 94
5 15 25 35 45 55 65 75 85 95
6 16 26 36 46 56 66 76 86 96
7 17 27 37 47 57 67 77 87 97
8 18 28 37 48 57 68 78 88 98
9 19 29 39 49 59 69 79 89 99
10 20 30 40 50 60 70 80 90 100

इरेटॉस्थेनिझच्या चाळणीचा हा गणनविधी संगणकीय कार्यक्रमणाद्वारे पार पाडण्यासाठी लागणारा वेळ आणि संगणकीय स्मृतीतील जागा यांचा विचार करून वरील प्रक्रियेत सुधारणा करून कमी गुंतागुंतीचे गणनविधी तयार केले जात आहेत.

संदर्भ :

  • Burton, David, M. Elementary Number Theory– 6th ed., McGraw-Hill, New York (2007).

समीक्षक : अनुराधा गर्गे