अभाज्य संख्याएँ और छलनी का विचार
अभाज्य संख्या वह संख्या है जो 1 से बड़ी हो और जिसके भाजक केवल 1 और वह स्वयं हों: 2, 3, 5, 7, 11 … 1 से बड़ी बाकी सब संख्याएँ भाज्य (संयुक्त) हैं, यानी उनका कोई छोटा भाजक होता है।
एक संख्या n जाँचनी हो तो उसे 2, 3, 4 … से √n तक भाग देकर देखो। पर अगर n तक की सारी अभाज्य संख्याएँ चाहिए, तो 2000 साल से भी पहले यूनानी विद्वान एराटोस्थनीज़ ने तेज़ तरीका सोचा: संख्याएँ जाँचो मत, जो अभाज्य नहीं हो सकतीं उन्हें हटाओ।
एल्गोरिदम चरण-दर-चरण
- 2 से n तक सब संख्याएँ लिखो। सबको "शायद अभाज्य" चिह्नित करो।
- सबसे छोटी चिह्नित संख्या p लो। वह अभाज्य है।
- उसके गुणज p², p² + p, p² + 2p, … n तक काट दो।
- चरण 2 पर लौटो। जब p × p, n से बड़ा हो जाए तो रुक जाओ।
- जो संख्याएँ कटी नहीं, वे सब अभाज्य हैं।
p² से ही क्यों शुरू करें? 5 × 3 जैसा छोटा गुणज 3 के समय पहले ही कट चुका है। हर भाज्य संख्या का एक अभाज्य गुणनखंड उसके वर्गमूल से छोटा या बराबर होता है, इसलिए √n तक की अभाज्य संख्याएँ काफ़ी हैं।
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False
p = 2
while p * p <= n:
if is_prime[p]:
for m in range(p * p, n + 1, p):
is_prime[m] = False
p += 1गति: लगभग n log log n चरण, यानी लगभग रैखिक। n = 1 करोड़ के लिए भी पलक झपकते खत्म। कीमत: n झंडों जितनी मेमोरी।
लंबे अंकगणित की ज़रूरत क्यों?
आम पूर्णांक चर में सीमित संख्या ही आ सकती है। 64-बिट चिह्नित पूर्णांक लगभग 9.2 × 10¹⁸ पर रुक जाता है, जिसमें 19 अंक हैं। पर 21! में 20 अंक हैं और 100! में 158 अंक। ऐसी संख्याओं के लिए हम लंबा अंकगणित इस्तेमाल करते हैं: संख्या को अंकों की सूची में रखो (अक्सर सबसे छोटा अंक पहले) और स्कूल वाली विधियाँ इस सूची पर चलाओ।
सूची उतनी लंबी हो सकती है जितनी मेमोरी हो। (पायथन जैसी कई भाषाओं में यह पहले से मौजूद है; यह जानना ज़रूरी है कि यह कैसे काम करता है।)
लंबी संख्याओं का जोड़, घटाव और गुणा
जोड़। दाईं ओर से चलो। हर कॉलम में s = a + b + हासिल निकालो। s mod 10 (s का आखिरी अंक) लिखो। नया हासिल s ÷ 10 का पूर्ण भाग है। अंत में हासिल 0 न हो तो उसे नया पहला अंक लिख दो। लागत: हर अंक पर एक चरण, O(n)।
घटाव (बड़ा − छोटा) इसी तरह होता है, पर हासिल की जगह उधार होता है: अंक छोटा हो तो अगले कॉलम से 10 उधार लो।
लंबी संख्या × छोटी संख्या। हर अंक के लिए d × k + हासिल निकालो, आखिरी अंक लिखो और बाकी हासिल दो। इसी से 50! जैसे क्रमगुणित बनते हैं: लंबी संख्या को 2 से, फिर 3 से, फिर 4 से गुणा करते जाओ।
लंबी × लंबी स्कूल वाले गुणा जैसा है: एक संख्या का हर अंक दूसरी के हर अंक से मिलता है, लगभग n × m चरण।
करके देखो: कॉलम से जोड़ो, फिर हाथ से छलनी चलाओ
1) कागज़ पर 2 से 50 तक की संख्याएँ 7 × 7 के खानों में लिखो। लाल पेंसिल से बिल्कुल वही करो जो 3D में हुआ। गिनो कितनी संख्याएँ बचीं। (15 आने चाहिए।) 2) 3D में कॉलम स्लाइडर चलाओ और 874965 + 365879 का हर कॉलम उत्तर देखने से पहले पेंसिल से जाँचो।
मुख्य सूत्र और परिभाषाएँ
- छलनी: p², p² + p, p² + 2p, … n तक काटो; जब p² > n हो जाए तो रुको
- छलनी का समय ≈ n log log n
- लंबा जोड़, हर कॉलम: s = a + b + हासिल; अंक = s mod 10; हासिल = ⌊s / 10⌋
- लंबा × छोटा: s = d × k + हासिल; अंक = s mod 10; हासिल = ⌊s / 10⌋
- संख्या N के अंकों की संख्या ≈ ⌊log₁₀ N⌋ + 1
हल किए गए उदाहरण
1. छलनी से 30 तक की अभाज्य संख्याएँ निकालो। किन अभाज्य संख्याओं के गुणज काटने पड़ते हैं?
p = 2, 3, 5 देखो (क्योंकि 5 × 5 = 25 ≤ 30, पर 7 × 7 = 49 > 30)। 2, 3 और 5 के गुणज काटो। बचीं: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29। ये 10 अभाज्य संख्याएँ हैं।
2. n = 50 के लिए p = 5 पर हम किस संख्या से काटना शुरू करते हैं? कटने वाली संख्याएँ लिखो।
हम 5² = 25 से शुरू करते हैं। कटती हैं 25, 30, 35, 40, 45, 50। (10, 15 और 20 पहले ही 2 और 3 से कट चुकी थीं।)
3. n = 100 के लिए कौन-सी अभाज्य संख्याएँ p लेनी पड़ेंगी और कितनी अभाज्य बचेंगी?
जिन अभाज्य p के लिए p × p ≤ 100, यानी p ≤ 10: ये 2, 3, 5 और 7 हैं (4 चरण)। फिर 100 से छोटी 25 अभाज्य संख्याएँ बचती हैं।
4. कॉलम से 478 + 595 जोड़ो।
इकाई: 8 + 5 = 13, 3 लिखो, हासिल 1। दहाई: 7 + 9 + 1 = 17, 7 लिखो, हासिल 1। सैकड़ा: 4 + 5 + 1 = 10, 0 लिखो, हासिल 1। हासिल 1 आगे आ गया: 1073।
5. कॉलम से (दाईं ओर से) 874965 + 365879 जोड़ो।
5 + 9 = 14 → 4, हासिल 1। 6 + 7 + 1 = 14 → 4, हासिल 1। 9 + 8 + 1 = 18 → 8, हासिल 1। 4 + 5 + 1 = 10 → 0, हासिल 1। 7 + 6 + 1 = 14 → 4, हासिल 1। 8 + 3 + 1 = 12 → 2, हासिल 1। आख़िरी हासिल 1 सबसे आगे: 1240844।
6. लंबी संख्या 468 को 7 से अंक-अंक करके गुणा करो।
दाईं ओर से: 8 × 7 = 56 → 6 लिखो, हासिल 5। 6 × 7 + 5 = 47 → 7 लिखो, हासिल 4। 4 × 7 + 4 = 32 → 2 लिखो, हासिल 3। हासिल 3 आगे: 3276।
7. 2⁶⁴ में कितने अंक हैं?
2⁶⁴ = 18446744073709551616। लघुगणक से जाँचो: 64 × log₁₀ 2 = 64 × 0.30103 = 19.27, इसलिए ⌊19.27⌋ + 1 = 20 अंक।
आम गलतियाँ
- p² की जगह 2p से काटना शुरू करना। उत्तर सही आता है पर चरण बेकार जाते हैं।
- अभाज्य संख्या को ही काट देना। हम सिर्फ़ उसके गुणज काटते हैं, p को नहीं।
- √n के बाद भी छलनी चलाते रहना। इसकी ज़रूरत नहीं और समय बर्बाद होता है।
- लंबे जोड़ में आख़िरी हासिल भूल जाना, जिससे 99 + 1 का उत्तर 100 की जगह 00 आता है।