सीमाहीन प्राइम की गणना करने के तरीके

ठीक है, तो शायद मुझे इस सवाल को बहुत कम नहीं करना चाहिए था ... मैंने पोस्ट को पहले 10000 प्राइम ढूंढने का सबसे प्रभावी तरीका । मैं सभी संभावित तरीकों की तलाश में हूं। लक्ष्य प्राथमिकता परीक्षणों के लिए एक स्टॉप शॉप होना है। प्राइम नंबर खोजने के लिए लोगों को पता है कि किसी भी और सभी परीक्षणों का स्वागत है।

इसलिए:

  • प्राइम ढूंढने के सभी अलग-अलग तरीके क्या हैं?
0
ro fr bn
ध्यान दें कि आप उन सभी की गणना किए बिना नीचे दिए गए प्राइम्स की संख्या को गिन सकते हैं: en.wikipedia.org/wiki/…
जोड़ा लेखक Jeffrey Bosboom, स्रोत

8 उत्तर

एक रूटर ग्रेड के छात्र ने हाल ही में एक पुनरावृत्ति संबंध जो प्राइम उत्पन्न करता है </एक>। इसके लगातार संख्याओं का अंतर या तो प्राइम्स या 1 उत्पन्न करेगा।

a(1) = 7
a(n) = a(n-1) + gcd(n,a(n-1)). 

यह बहुत सारे बकवास बनाता है जिसे फ़िल्टर करने की आवश्यकता होती है। बेनोइट क्लॉइट्रे में भी यह पुनरावृत्ति है जो एक समान कार्य करता है:

b(1) = 1
b(n) = b(n-1) + lcm(n,b(n-1))

फिर लगातार संख्याओं का अनुपात, शून्य एक [बी (एन) / बी (एन -1) -1] प्रमुख है। इन सब का एक पूरा खाता

रिकर्सिविटी

चलनी के लिए, आप हर बार एक जोड़ने के बजाए एक व्हील का उपयोग करके बेहतर कर सकते हैं, बेहतर वृद्धिशील प्राइम नंबर स्विस । यहां एक पहिया का एक उदाहरण है। चलो अनदेखा करने के लिए संख्याओं, 2 और 5 को देखें। उनका पहिया है, [2,4,2,2]।

0
जोड़ा

The Sieve of Eratosthenes is a decent algorithm:

  1. Take the list of positive integers 2 to any given Ceiling.
  2. Take the next item in the list (2 in the first iteration) and remove all multiples of it (beyond the first) from the list.
  3. Repeat step two until you reach the given Ceiling.
  4. Your list is now composed purely of primes.

इस एल्गोरिदम के लिए एक कार्यात्मक सीमा है जिसमें यह स्मृति के लिए गति का आदान-प्रदान करता है। प्राइम्स की बहुत बड़ी सूचियां उत्पन्न करते समय स्मृति क्षमता को स्काइरोकेट की आवश्यकता होती है।

0
जोड़ा
महत्वपूर्ण विवरण यहां गायब है: आप कैसे पाते हैं, और आप गुणकों को "हटाएं" कैसे करते हैं। यदि आप उन्हें उचित तरीके से पाते हैं, यानी उस प्राइम के चरणों में प्राइम से गिनती करना, आप उन्हें बिल्कुल भी नहीं हटा सकते , क्योंकि तब आप गिन सकते हैं । एसओई का बिंदु अंकन गुणक है, उनके मान के रूप में पते के रूप में मूल्यों की तुलना किए बिना (इस प्रकार अतिरिक्त log n से परहेज करता है जटिलता में कारक)। यह वही है जो तुलनात्मक प्रकारों की तुलना में पूर्णांक को तेज बनाता है। यदि आप वास्तव में उन्हें हटा रहे हैं हैं तो आप उस लाभ को छोड़ देते है
जोड़ा लेखक Will Ness, स्रोत

दिए गए पूर्णांक के लिए, सबसे तेज़ प्राथमिकता जांच मुझे पता है:

  1. Take a list of 2 to the square root of the integer.
  2. Loop through the list, taking the remainder of the integer / current number
    1. If the remainder is zero for any number in the list, then the integer is not prime.
    2. If the remainder was non-zero for all numbers in the list, then the integer is prime.

यह इरेटोस्टेनेस की चलनी की तुलना में काफी कम स्मृति का उपयोग करता है और आम तौर पर व्यक्तिगत संख्याओं के लिए तेज़ होता है।

0
जोड़ा

@theprise

अगर मैं तत्काल सूची (बड़ी संख्या के लिए स्मृति के साथ समस्याओं ...) की बजाय वृद्धिशील लूप का उपयोग करना चाहता था, तो सूची बनाने के बिना ऐसा करने का एक अच्छा तरीका क्या होगा?

ऐसा लगता है कि सामान्य संख्या (एन% एक्स) की जांच के मुकाबले दिए गए पूर्णांक (एक्स% 3) के लिए विभाज्यता जांच करना सस्ता होगा।

0
जोड़ा

यदि आप प्राइम नंबर जेनरेट करने का कोई तरीका ढूंढना चाहते हैं, तो इसे पिछला प्रश्न

0
जोड़ा

पूर्णांक की जड़ से 2 तक सूची का उपयोग करके आपके एल्गोरिदम में, आप केवल 2 के बाद विषम संख्याओं का परीक्षण करके प्रदर्शन में सुधार कर सकते हैं। यानी, आपकी सूची में केवल 2 और सभी विषम संख्याएं पूर्णांक के वर्ग रूट से 3 तक की आवश्यकता होती है । यह किसी और जटिलता को पेश किए बिना आधे गुना में कटौती करता है।

0
जोड़ा

@ अकोम का सवाल मुझे:

लूपिंग मेरे पिछले सुझाव पर ठीक काम करेगी, और आपको यह निर्धारित करने के लिए कोई गणना करने की आवश्यकता नहीं है कि कोई संख्या भी है; अपने लूप में, नीचे दिखाए गए अनुसार, प्रत्येक भी संख्या को छोड़ दें:

//Assuming theInteger is the number to be tested for primality.
// Check if theInteger is divisible by 2.  If not, run this loop.
//  This loop skips all even numbers.
for( int i = 3; i < sqrt(theInteger); i + 2) 
{
    if( theInteger % i == 0) 
    {
       //getting here denotes that theInteger is not prime 
       // somehow indicate that some number, i, divides it and break
       break;
    }
}
0
जोड़ा

कुछ प्राइम टेस्ट केवल कुछ संख्याओं के साथ काम करते हैं, उदाहरण के लिए, लुकास? लेमर </ए> परीक्षण केवल मेर्सन संख्याओं के लिए काम करता है।

बड़ी संख्या के लिए उपयोग किए जाने वाले अधिकांश प्रमुख परीक्षण केवल आपको बता सकते हैं कि एक निश्चित संख्या "शायद प्रधान" है (या, यदि संख्या परीक्षण में विफल हो जाती है, तो यह निश्चित रूप से नहीं प्रधान) है। आम तौर पर आप एल्गोरिदम जारी रख सकते हैं जब तक कि आपके पास प्राइम होने की संख्या की बहुत अधिक संभावना न हो।

यह पृष्ठ और विशेष रूप से इसके "यह भी देखें" अनुभाग पर एक नज़र डालें।

मिलर-राबिन परीक्षण , मुझे लगता है, सबसे अच्छे परीक्षणों में से एक है। अपने मानक रूप में यह आपको संभावित प्राइम देता है - हालांकि यह दिखाया गया है कि यदि आप 3.4 * 10 ^ 14 के नीचे एक संख्या में परीक्षण लागू करते हैं, और यह प्रत्येक पैरामीटर 2, 3, 5, 7, 11, 13 के लिए परीक्षण पास करता है और 17, यह निश्चित रूप से प्रधान है।

एकेएस परीक्षण पहला निर्धारक, सिद्ध, सामान्य, बहुपद-समय परीक्षण था। हालांकि, मेरे सबसे अच्छे ज्ञान के लिए, इसका सर्वोत्तम कार्यान्वयन अन्य परीक्षणों की तुलना में धीमा हो जाता है जब तक इनपुट हास्यास्पद रूप से बड़ा न हो।

0
जोड़ा