एराटोस्थनीज़ की छलनी के बारे में - अभाज्य छलनी कैसे काम करती है

कुरीन के एराटोस्थनीज़

एराटोस्थनीज़ लगभग 276 से 194 ईसा पूर्व तक जीवित रहे और अलेक्ज़ेंड्रिया के महान पुस्तकालय के प्रमुख थे। वे सबसे अधिक इस बात के लिए जाने जाते हैं कि उन्होंने दो शहरों में परछाइयों की लंबाई से पृथ्वी का आकार मापा। छलनी का नाम उन पर इसलिए है क्योंकि गेरासा के निकोमाकस ने लगभग 100 ईस्वी में लिखी अपनी पुस्तक अंकगणित का परिचय में इसे उनकी विधि बताया।

छलनी कैसे काम करती है

2 से N तक की संख्याएँ लिखें। पहली संख्या 2 अभाज्य है: 4, 6, 8 और 2 के बाकी सभी गुणज काटें। अगली बची संख्या 3 अभाज्य है: 9, 12, 15 आदि काटें। 5, 7 और अगली बची संख्याओं के साथ जारी रखें। जो संख्या कभी नहीं कटती, उसका कोई छोटा गुणनखंड नहीं होता, इसलिए वह अभाज्य है।

वर्गमूल पर रुकें

N तक की हर भाज्य संख्या का एक अभाज्य गुणनखंड होता है जो N के वर्गमूल से बड़ा नहीं होता। इसलिए जैसे ही p², N से बड़ा हो जाता है, काटने को कुछ नहीं बचता। 100 तक के अभाज्यों के लिए केवल 2, 3, 5 और 7 चाहिए, और 1000 के लिए 31 तक के अभाज्य।

यह कितनी तेज़ है?

छलनी को लगभग N log log N चरण लगते हैं, जो N से बस थोड़ा तेज़ बढ़ता है। कंप्यूटर आज भी इसका उपयोग करते हैं, अक्सर टुकड़ों में खंडित छलनी के रूप में, ताकि अरबों तक की अभाज्य संख्याएँ सूचीबद्ध की जा सकें। किसी एक बड़ी संख्या के अभाज्य होने की जाँच के लिए दूसरी विधियाँ तेज़ हैं।

अक्सर पूछे जाने वाले प्रश्न

एराटोस्थनीज़ की छलनी का आविष्कार किसने किया?

इसका नाम तीसरी शताब्दी ईसा पूर्व के यूनानी विद्वान कुरीन के एराटोस्थनीज़ पर रखा गया है। सबसे पुराना लिखित विवरण लगभग 100 ईस्वी में गेरासा के निकोमाकस का है।

छलनी p² से काटना क्यों शुरू करती है?

p के हर छोटे गुणज का एक छोटा अभाज्य गुणनखंड होता है, इसलिए किसी छोटे अभाज्य ने उसे पहले ही काट दिया है।

1000 से कम कितनी अभाज्य संख्याएँ हैं?

1000 से कम 168 अभाज्य संख्याएँ हैं। सबसे बड़ी 997 है।