ओ (लॉग एन) के लिए सादगी एल्गोरिथ्म

सादगी की परीक्षा

यह निर्धारित करने के लिए कि क्या दी गई संख्या N सरल है, यह निश्चित रूप से N के विभाजकों के लिए एक सरल खोज चक्र लिखने के लिए पर्याप्त है:

bool prime(long long n){ for(long long i=2;i<=sqrt(n);i++) if(n%i==0) return false; return true; } 

सादगी के लिए एक नंबर की जाँच करने का यह कार्य काफी प्रभावी है - इसके संचालन का विषम व्यवहार ओ (sqrt (N)) है । हालांकि, कभी-कभी खेल प्रोग्रामिंग में आपको सादगी के लिए संख्या को तेजी से जांचने में सक्षम होना चाहिए।

कुछ मामलों में, जब एक निश्चित सीमा से संख्याओं के लिए ऐसा चेक करना आवश्यक होता है, तो Sieve of Eratosthenes एल्गोरिथ्म का उपयोग करना उचित होता है।

इस लेख में, मैं एकल सादगी परीक्षण करने के लिए एक और तरीका पर विचार करूंगा - त्वचा परीक्षण ।

फ़र्मेट के परीक्षण के साथ ओ (लॉग एन) के लिए एक संभाव्य एल्गोरिथ्म

फ़र्मेट परीक्षण के लिए गणितीय तर्क काफी हद तक यहाँ वर्णित है ।

मैं C ++ में इसका विशिष्ट कार्यान्वयन करूंगा, और यह भी दिखाऊंगा कि किसी पावर को बढ़ाते समय लंबे लंबे प्रकार के ओवरफ्लो से कैसे निपटें।

फार्म टेस्ट

त्रुटि की पर्याप्त रूप से अच्छी संभावना के साथ सादगी के लिए संख्या एन की जांच करने के लिए, फ़र्मेट परीक्षण के साथ यादृच्छिक संख्या ए 100 बार जांचना पर्याप्त है:


यह भी ध्यान देने योग्य है कि संख्या ए और एन को कॉपीटाइम होना चाहिए। यदि यह स्थिति संतुष्ट नहीं है, तो संख्या एन स्पष्ट रूप से सरल नहीं है।

 bool ferma(long long x){ if(x == 2) return true; srand(time(NULL)); for(int i=0;i<100;i++){ long long a = (rand() % (x - 2)) + 2; if (gcd(a, x) != 1) return false; if( pows(a, x-1, x) != 1) return false; } return true; } 

मैं ध्यान देता हूं कि यह सत्यापन फ़ंक्शन GCD को खोजने के कार्यों का उपयोग करता है, साथ ही एक पावर मोडुलो को त्वरित रूप से बढ़ाता है।

जीसीडी खोज रहे हैं

दरअसल, GCD खोजने में सबसे कम समस्याएँ होती हैं। हम यूक्लिडियन एल्गोरिथ्म का उपयोग करते हैं :

 long long gcd(long long a, long long b){ if(b==0) return a; return gcd(b, a%b); } 

तेजी से घातांक मोडुलो

तेजी से घातांक (बाइनरी) काफी व्यापक रूप से जाना जाता है। मैं केवल यह नोट करता हूं कि जब दो प्रकार की संख्याओं को लंबे समय तक बढ़ाया जाता है, तो परिणाम का एक अतिप्रवाह तब भी हो सकता है जब हम परिणाम मोड्यूल लेते हैं। इसलिए, हम दो नंबरों के बाइनरी गुणा फ़ंक्शन का भी उपयोग करते हैं। इसका अर्थ बहुत तेजी से घातांक के समान है।

 long long mul(long long a, long long b, long long m){ if(b==1) return a; if(b%2==0){ long long t = mul(a, b/2, m); return (2 * t) % m; } return (mul(a, b-1, m) + a) % m; } long long pows(long long a, long long b, long long m){ if(b==0) return 1; if(b%2==0){ long long t = pows(a, b/2, m); return mul(t , t, m) % m; } return ( mul(pows(a, b-1, m) , a, m)) % m; } 

उसी तरह जैसे किसी पावर को बढ़ाते समय, अगर दूसरा फैक्टर भी है, तो आप इसे 2 से विभाजित कर सकते हैं, और ए और बी / 2 की संख्या की गणना करने के लिए आगे बढ़ सकते हैं। अन्यथा, आपको संख्या ए और बी - 1 के उत्पाद की गणना करने की आवश्यकता है।

समाधान के एसिम्पोटिक्स

सादगी परीक्षण के अंतिम स्पर्शोन्मुखता हे (K * log N * log N) है , जहां K Fermat परीक्षण की पुनरावृत्तियों की संख्या है, जो आमतौर पर 100 है। यदि आप सादगी के लिए कई प्रकार के इंट की जांच करना चाहते हैं, तो आप बाइनरी गुणा के बिना कर सकते हैं। फिर सादगी की जांच के एसिम्पोटिक्स ओ (के * लॉग एन) होंगे ।