🏮 🥝 🤤 एन पहला प्रमुख नंबर खोजने के लिए एल्गोरिथ्म 👶🏼 ☝️ 🍍

प्रोग्रामिंग सिखाने की प्रक्रिया में, मुझे 1M पहले प्राइम्स खोजने का काम मिला।

Habré पर पहले से ही एक बार इसके बारे में लिखा था। लेकिन, सबसे अधिक बार, यह संख्या एन तक सभी अपराधों को खोजने के बारे में था । मैं इस बारे में बात करूंगा कि कैसे मैंने एन पहले प्राइम नंबर खोजने की समस्या को हल किया।

पहली नज़र में, ऐसा लग सकता है कि इन कार्यों में व्यावहारिक रूप से कोई अंतर नहीं है। और यह वास्तव में ऐसा है, जब तक हम यह नहीं समझते हैं कि विभाजकों की गणना करना एक बेहद खराब काम है।

किए गए कार्य के परिणामस्वरूप, मुझे 1 मिलियन प्राइम खोजने में केवल 0.262 सेकंड लगते हैं, जो निश्चित रूप से, सीमा नहीं है, लेकिन यह पहले से ही प्रभावशाली है। एल्गोरिथ्म C ++ में लागू किया गया है।

प्राइम नंबरों पर पिछले लेख के लेखक की तरह, मैंने समस्या को हल करना शुरू किया। तो, अभाज्य संख्या p यह है कि इसके दो भाजक हैं - एक और p । पहली बात जो ध्यान में आती है वह यह है कि प्रत्येक संख्या को पिछले सभी संख्याओं से विभाजित करके जांचना।

विचार बुरा निकला। एक लाख सरल की खोज में कार्यक्रम के पहले 30 मिनट के बाद मुझे इसका एहसास हुआ। परिणाम इस प्रकार हैं:

10,000 - 2,349 एस।
100,000 - 293.552 एस
1,000,000 - इंतजार नहीं किया

जैसा कि पहले ही ऊपर वर्णित लेख में, मैंने एल्गोरिथ्म को अनुकूलित करने के बारे में निर्धारित किया है। सबसे पहले, यह भी संख्याओं की जांच करने के लिए कोई मतलब नहीं है, क्योंकि 2 ही एकमात्र प्रमुख संख्या है। डिवाइडर के साथ भी - आप लोगों के लिए भी जांच नहीं कर सकते। तीसरे, विभाजक के रूप में यह संख्या को लेने के लिए पर्याप्त है न कि जाँच की गई आधी संख्या से अधिक। यहाँ यह आया है:

// Listing 1 #include <iostream> #include <vector> #include <ctime> using namespace std ; int main ( ) { clock_t start = clock ( ) ; const int AIM = 10000 ; vector < int > prime_nums ; prime_nums. push_back ( 2 ) ; for ( int num = 3 ; prime_nums. size ( ) < AIM ; num + = 2 ) { bool isprime = true ; for ( int i = 3 ; i <= num / 2 ; i + = 2 ) { if ( num % i == 0 ) { isprime = false ; break ; } } if ( isprime ) prime_nums. push_back ( num ) ; } cout << prime_nums [ AIM - 1 ] ; clock_t end = clock ( ) ; cout << " \n ----------------" << endl ; cout << "Time: " << double ( end - start ) / CLOCKS_PER_SEC << " sec" << endl ; }

यह बेहतर हुआ, लेकिन मैं अभी भी एक मिलियन के लिए इंतजार नहीं कर सकता था
10,000 - 0,589 एस।
100,000 - 72.662 एस
1,000,000 - 20 मिनट के बाद मैंने इंतजार करना बंद कर दिया

यह स्पष्ट है कि आप इस एल्गोरिथ्म को लंबे समय तक अनुकूलित करना जारी रख सकते हैं, जो कि मैंने मूल रूप से किया था। आप 5 और 0. में समाप्त होने वाली संख्याओं की जांच नहीं कर सकते। आप सबसे सामान्य दिव्यांगों की सूची बना सकते हैं और उन पर पहले प्रत्येक संख्या की जांच कर सकते हैं। कुछ बिंदु पर, यह मुझे लग रहा था कि मैं केवल पहले से पाए गए अपराधों पर नए नंबर की जांच करके समस्या को हल कर सकता हूं। यह महत्वपूर्ण परिणाम नहीं लाया। समस्या यह थी कि प्रत्येक नए नंबर के साथ, चेक की संख्या में वृद्धि हुई, और विभाजन ऑपरेशन सबसे कठिन में से एक है।

मैं खोज में निकला। मैंने एराटोस्थनीज की छलनी के बारे में जाना। लेकिन मैं एल्गोरिथ्म का उपयोग नहीं कर सकता क्योंकि यह मेरे कार्य के लिए है। यह पहले से ज्ञात नहीं है * एन प्राइम्स खोजने के लिए आपको कितनी संख्या में झारना है। इसलिए, मैंने अपनी आवश्यकताओं के अनुसार एल्गोरिथ्म को संशोधित करने का निर्णय लिया।

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

// Listing 2 #include <iostream> #include <ctime> #include <vector> using namespace std ; int main ( ) { clock_t start = clock ( ) ; const int AIM = 1000000 ; int startSize = AIM ; // int addSize = AIM ; // vector < bool > nums ( startSize ) ; vector < int > primeNums ( AIM ) ; int foundPrimes = 0 ; for ( int i = 2 ; i < startSize ; i ++ ) nums [ i ] = true ; bool addition = false ; int adder = 0 ; while ( true ) { if ( addition ) { nums. resize ( nums. size ( ) + addSize, true ) ; // for ( int i = 0 ; i < foundPrimes ; i ++ ) { int cur_num = primeNums [ i ] ; if ( ( addSize + ( ( nums. size ( ) - addSize ) % cur_num ) ) < cur_num ) continue ; for ( int j = ( ( nums. size ( ) - addSize ) / cur_num ) * cur_num ; j < nums. size ( ) ; j + = cur_num ) nums [ j ] = false ; } } else addition = true ; int iter ; if ( foundPrimes == 0 ) iter = 2 ; else iter = primeNums [ foundPrimes - 1 ] + 2 ; for ( ; iter < nums. size ( ) ; iter ++ ) { // if ( nums [ iter ] ) { primeNums [ foundPrimes ] = iter ; foundPrimes ++ ; if ( foundPrimes == AIM ) break ; // for ( int j = iter + iter ; j < nums. size ( ) ; j + = iter ) nums [ j ] = false ; } else continue ; } if ( foundPrimes == AIM ) break ; } cout << "Last prime: " << primeNums [ AIM - 1 ] ; clock_t end = clock ( ) ; cout << " \n ----------------" << endl ; cout << "Time: " << double ( end - start ) / CLOCKS_PER_SEC << " sec" << endl ; return 0 ; }

परिणाम थोड़ा आश्चर्यचकित थे:
10,000 - 0.001 एस।
100,000 - 0.021 एस।
1,000,000 - 0,262 एस।
...
10,000,000 - 2,999 एस।

इस पर, 1 एम पहले अपराधों को खोजने के कार्य के साथ, मैं समाप्त हो गया। परिणाम ने मुझे पूरी तरह से संतुष्ट किया। लेकिन और क्या किया जा सकता है? आप Eratosthenes की छलनी के आधार पर किसी भी ज्ञात एल्गोरिदम को लागू कर सकते हैं, उदाहरण के लिए, सुंदरम छलनी । लेकिन परिणाम महत्वपूर्ण रूप से बदलने की संभावना नहीं है। शायद एटकिन छलनी खुद को बेहतर दिखाने में सक्षम होगी - यह इस एल्गोरिथ्म है जो आधुनिक क्रिप्टोग्राफी में सबसे अधिक बार उपयोग किया जाता है।

* - मेरे लिए अज्ञात। हेलाविन ने पहली टिप्पणी में कहा कि लंबे समय से क्या जाना जाता है।

युपीडी
स्मृति की खपत के बारे में, वर्णित एल्गोरिदम निम्नानुसार व्यवहार करते हैं:

1 मिलियन प्राइम्स, अधिकतम रैम
- जानवर बल विभक्त: ~ 4Mb
- एराटोस्थनीज की संशोधित छलनी: ~ 6Mb

10 मिलियन प्राइम, अधिकतम रैम
- जानवर बल विभक्त: ~ 39Mb
- एराटोस्थनीज की संशोधित छलनी: ~ 61Mb

एन पहला प्रमुख नंबर खोजने के लिए एल्गोरिथ्म

More articles: