पायथन में संख्याओं की प्राथमिकता की जांच करने के लिए मेरा वर्तमान एल्गोरिदम 10 मिलियन से 1 अरब के बीच की संख्या को धीमा करने का तरीका है। मैं यह जानना चाहता हूं कि मुझे कभी भी 1 अरब से अधिक संख्याएं नहीं मिलेंगी।जल्दी से निर्धारित करें कि संख्याओं के लिए पायथन में कोई संख्या प्रमुख है <1 अरब
संदर्भ यह है कि मुझे प्रोजेक्ट यूलर की समस्या 60 को हल करने के लिए पर्याप्त कार्यान्वयन नहीं मिल सकता है: मुझे 75 सेकंड में समस्या का उत्तर मिल रहा है जहां मुझे इसे 60 सेकंड में चाहिए। http://projecteuler.net/index.php?section=problems&id=60
मेरे पास मेरे निपटारे में बहुत कम स्मृति है इसलिए मैं 1 अरब से नीचे के सभी प्राइम नंबरों को स्टोर नहीं कर सकता।
मैं वर्तमान में 6k ± 1 के साथ ट्यून किए गए मानक परीक्षण प्रभाग का उपयोग कर रहा हूं। क्या इससे कुछ बेहतर है? क्या मुझे पहले से ही संख्याओं के लिए राबिन-मिलर विधि प्राप्त करने की आवश्यकता है जो इस बड़े हैं।
primes_under_100 = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
def isprime(n):
if n <= 100:
return n in primes_under_100
if n % 2 == 0 or n % 3 == 0:
return False
for f in range(5, int(n ** .5), 6):
if n % f == 0 or n % (f + 2) == 0:
return False
return True
मैं इस एल्गोरिदम को कैसे सुधार सकता हूं?
प्रेसिजन: मैं अजगर के लिए नया हूं और केवल पाइथन 3+ के साथ काम करना चाहता हूं।
अंतिम कोड
जो लोग रुचि रखते हैं, MAK के विचारों का उपयोग कर के लिए, मैं निम्नलिखित कोड तेज है जो 1/3 के बारे में उत्पन्न, मुझे भी कम समय में यूलर समस्या के परिणाम प्राप्त करने के लिए अनुमति देता है 60 सेकंड से अधिक!
from bisect import bisect_left
# sqrt(1000000000) = 31622
__primes = sieve(31622)
def is_prime(n):
# if prime is already in the list, just pick it
if n <= 31622:
i = bisect_left(__primes, n)
return i != len(__primes) and __primes[i] == n
# Divide by each known prime
limit = int(n ** .5)
for p in __primes:
if p > limit: return True
if n % p == 0: return False
# fall back on trial division if n > 1 billion
for f in range(31627, limit, 6): # 31627 is the next prime
if n % f == 0 or n % (f + 4) == 0:
return False
return True
यह Py3k ??? – st0le
मुझे इसे पायथन 3 या पायथन 3.1 नाम से पता था, लेकिन ऐसा लगता है कि Py3k इन संस्करणों का संदर्भ देता है। –
यह 'f' और' f + 4' नहीं होना चाहिए ... क्या आप पुष्टि कर सकते हैं? क्यों '4'? – st0le