जावा

Question

में रहस्यमय isPrime विधि निम्न विधि पर विचार करें:

public static boolean isPrime(int n) { 
    return ! (new String(new char[n])).matches(".?|(..+?)\\1+"); 
} 

मैं रेगुलर एक्सप्रेशन गुरु कभी नहीं किया गया है, इसलिए किसी को भी पूरी तरह से कैसे इस पद्धति वास्तव में काम करता है व्याख्या कर सकते हैं? इसके अलावा, यह निर्धारित करने के लिए कि क्या एक पूर्णांक प्रमुख है, अन्य संभावित तरीकों की तुलना में यह कुशल है?

Answer 1

सबसे पहले, ध्यान दें कि इस regex एक एकल गिनती प्रणाली में प्रतिनिधित्व संख्या पर लागू होता है, अर्थात

1  is 1 
11  is 2 
111  is 3 
1111 is 4 
11111 is 5 
111111 is 6 
1111111 is 7 

और इतने पर। वास्तव में, किसी भी चरित्र का उपयोग किया जा सकता है (इसलिए अभिव्यक्ति में . एस), लेकिन मैं "1" का उपयोग करूंगा।

दूसरा, ध्यान दें कि यह रेगेक्स समग्र (गैर-प्रधान) संख्याओं से मेल खाता है; इस प्रकार अस्वीकृति प्रारंभिकता का पता लगाती है।

---

स्पष्टीकरण:

अभिव्यक्ति की पहली छमाही,

.? 

का कहना है कि तार "" (0) और "1" (1) कर रहे हैं मैच, यानी प्राइम (परिभाषा के अनुसार, though arguable।)

सरल अंग्रेजी में दूसरा आधा, कहें एस:

सबसे छोटी स्ट्रिंग से मिलान करें जिसका लंबाई कम से कम 2 है, उदाहरण के लिए, "11" (2)। अब, देखें कि क्या हम इसे दोहराकर पूरी स्ट्रिंग से मेल खा सकते हैं। क्या "1111" (4) मैच है? क्या "111111" (6) मैच है? क्या "11111111" (8) मैच है? और इसी तरह। यदि नहीं, तो अगली छोटी स्ट्रिंग, "111" (3) के लिए फिर से प्रयास करें। आदि

अब आप देख सकते हैं कि, यदि मूल स्ट्रिंग एक कई अपने सबस्ट्रिंग के रूप में मिलान नहीं किया जा सकता है, तो परिभाषा के द्वारा, यह प्रधानमंत्री है!

बीटीडब्ल्यू, गैर-लालची ऑपरेटर ? वह है जो "एल्गोरिदम" को सबसे छोटा और गिनती से शुरू करता है।

---

क्षमता:

• @TeddHopp नोटों के रूप में, अच्छी तरह से:

  यह दिलचस्प है, लेकिन निश्चित रूप से कुशल नहीं, विभिन्न तर्क, जिनमें से कुछ मैं नीचे को मजबूत करेंगे द्वारा है अज्ञात चलनी-एराटोस्टेनेस दृष्टिकोण 4, 6, और 9 जैसे पूर्णांक के गुणकों की जांच करने के लिए परेशान नहीं होगा, 2 और 3 के गुणकों की जांच करते समय पहले से ही "दौरा" किया जा रहा है। हां, यह रेगेक्स दृष्टिकोण प्रत्येक छोटे पूर्णांक को पूरी तरह से जांचता है।

• @PetarMinchev नोट्स के रूप में, हम संख्या के वर्ग रूट तक पहुंचने के बाद गुणक-जांच योजना "शॉर्ट-सर्किट" कर सकते हैं। हमें ऐसा करने में सक्षम होना चाहिए क्योंकि वर्ग रूट की तुलना में अधिक वर्ग रूट की तुलना में कम के साथ साझेदार होना चाहिए (क्योंकि अन्यथा वर्ग रूट से अधिक दो कारक संख्या से अधिक उत्पाद उत्पन्न करेंगे), और यदि यह अधिक कारक मौजूद है, तो हमें कम कारक का सामना करना पड़ सकता था (और इस प्रकार, मिलान किया गया)।

• @Jesper और कटाई के साथ @Brian नोट के रूप में, एक गैर एल्गोरिथम दृष्टिकोण से, पर विचार कैसे एक रेगुलर एक्सप्रेशन स्मृति आवंटन स्ट्रिंग स्टोर करने के लिए, जैसे से शुरू होगाchar[9000] 9000 के लिए। अच्छा, यह आसान था, है ना? ;)

• @Foon नोट्स के रूप में, संभाव्य विधियां मौजूद हैं जो बड़ी संख्या के लिए अधिक कुशल हो सकती हैं, हालांकि वे हमेशा सही नहीं हो सकते हैं (इसके बजाय स्यूडोप्रिम्स को बदलना)। लेकिन ऐसे निर्धारक परीक्षण भी हैं जो चावल-आधारित तरीकों से 100% सटीक और कहीं अधिक कुशल हैं। Wolfram's का एक अच्छा सारांश है।

Answer 2

यह जांचने का वास्तव में एक प्रभावी तरीका नहीं है कि कोई संख्या प्रमुख है (यह प्रत्येक विभाजक की जांच करता है)।

sqrt(number) तक विभाजक की जांच करने का एक प्रभावी तरीका है। यह है कि यदि आप निश्चित होना चाहते हैं कि कोई संख्या प्रमुख है। अन्यथा संभावित संभाव्यता जांच हैं जो तेजी से हैं, लेकिन 100% सही नहीं हैं।

Answer 3

प्राइम की अनूठी विशेषताओं और क्यों यह काम पहले ही कवर हो चुका है।

public class Main { 

    public static void main(String[] args) { 
     long time = System.nanoTime(); 
     for (int i = 2; i < 10000; i++) { 
      isPrimeOld(i); 
     } 
     time = System.nanoTime() - time; 
     System.out.println(time + " ns (" + time/1000000 + " ms)"); 
     time = System.nanoTime(); 
     for (int i = 2; i < 10000; i++) { 
      isPrimeRegex(i); 
     } 
     time = System.nanoTime() - time; 
     System.out.println(time + " ns (" + time/1000000 + " ms)"); 
     System.out.println("Done"); 
    } 

    public static boolean isPrimeRegex(int n) { 
     return !(new String(new char[n])).matches(".?|(..+?)\\1+"); 
    } 

    public static boolean isPrimeOld(int n) { 
     if (n == 2) 
      return true; 
     if (n < 2) 
      return false; 
     if ((n & 1) == 0) 
      return false; 
     int limit = (int) Math.round(Math.sqrt(n)); 
     for (int i = 3; i <= limit; i += 2) { 
      if (n % i == 0) 
       return false; 
     } 
     return true; 
    } 
} 

इस परीक्षण की गणना करता है या नहीं, संख्या 9,999 से ऊपर प्रधानमंत्री है, 2. से शुरू और यहाँ एक अपेक्षाकृत शक्तिशाली सर्वर पर इसके उत्पादन है::

8537795 ns (8 ms) 
30842526146 ns (30842 ms) 
Done 

तो यहाँ पारंपरिक दृष्टिकोण और इस दृष्टिकोण का उपयोग कर एक परीक्षण है

तो संख्याएं पर्याप्त होने के बाद यह काफी अक्षम है। (999 तक, रेगेक्स लगभग 400 एमएस में चलता है।) छोटी संख्या के लिए, यह तेज़ है, लेकिन 9, 999 तक प्राइम जेनरेट करने के लिए अभी भी तेज़ है, पारंपरिक तरीके से 99 पुराने तरीके तक प्राइम भी उत्पन्न करना है (23 एमएस)।