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

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

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

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.

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

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

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.

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

@theprise

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

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

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

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

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

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

//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;
    }
}

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

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

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

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