प्राइम नंबर खोजने के लिए फास्ट एल्गोरिदम?

सबसे पहले - मैंने इस मंच में बहुत कुछ देखा है और मुझे कुछ कुछ तेज़ नहीं मिला है। मैं एक ऐसा फ़ंक्शन बनाने का प्रयास करता हूं जो मुझे निर्दिष्ट सीमा में प्रमुख संख्या देता है। उदाहरण के लिए मैंने एरैटोस्टेनेस की चलनी का उपयोग करके यह फ़ंक्शन (सी # में) किया था। मैं भी एटकिन की चलनी की कोशिश की लेकिन एरेटोस्थेनेज एक तेजी से चलाता है (मेरे कार्यान्वयन में):प्राइम नंबर खोजने के लिए फास्ट एल्गोरिदम?

public static void SetPrimesSieve(int Range) 
    { 
     Primes = new List<uint>(); 
     Primes.Add(2); 
     int Half = (Range - 1) >> 1; 
     BitArray Nums = new BitArray(Half, false); 
     int Sqrt = (int)Math.Sqrt(Range); 
     for (int i = 3, j; i <= Sqrt;) 
     { 
      for (j = ((i * i) >> 1) - 1; j < Half; j += i) 
       Nums[j] = true; 
      do 
       i += 2; 
      while (i <= Sqrt && Nums[(i >> 1) - 1]); 
     } 
     for (int i = 0; i < Half; ++i) 
      if (!Nums[i]) 
       Primes.Add((uint)(i << 1) + 3); 
    }

यह से कोड & एल्गोरिदम मैंने पाया दो बार तेजी के बारे में चलाता है ... वहाँ रूढ़ अंक खोजने के लिए एक तेज़ तरीका होना चाहिए, क्या आप मेरी मदद कर सकते हैं?

स्रोत

2010-09-27 Ohad

इन आप किस कीमत की तलाश कर रहे हैं? बस 0 और अधिकतम int के बीच? सीमा भी कितनी विस्तृत है? – Gleno

चलो अरब/2 – Ohad

जैसे कुछ कहें 10 एम 9 से कम 50 एम प्राइम्स हैं, इसलिए उन्हें प्रीकंप्यूटिंग करने से आपको 200 एमबी टेबल मिल जाएगी। यह वास्तव में चाकू को स्टोर करने के लिए छोटा होगा (10^9 बिट्स 125 एमबी है, और आपको यहां तक कि बिट्स को स्टोर करने की आवश्यकता नहीं है, ताकि आप इसे 64 एमबी के तहत फिट कर सकें)। – Gabe

इस विषय पर एल्गोरिदम के लिए खोज करते समय (प्रोजेक्ट यूलर के लिए) मुझे कुछ भी तेज़ी से ढूंढना याद नहीं है। यदि गति वास्तव में चिंता का विषय है, तो क्या आपने केवल प्राइम स्टोर करने के बारे में सोचा है ताकि आपको इसे देखने की आवश्यकता हो?

संपादित करें: त्वरित Google खोज this मिली, यह पुष्टि करते हुए कि सबसे तेज़ तरीका केवल परिणाम पृष्ठ पर होगा और आवश्यकतानुसार उन्हें देखें।

एक और संपादन - आपको अधिक जानकारी here मिल सकती है, अनिवार्य रूप से इस विषय का एक डुप्लिकेट। शीर्ष पद में कहा गया है कि फ्लाई पर पैदा होने तक एटकिन की चलनी युग की तुलना में तेज़ थी।

स्रोत

2010-09-27 21:57:22 jlv

नहीं, वे तेज़ नहीं हैं, यहां तक कि मेरा कोड तेज़ है। मैंने वास्तव में ऐसा कुछ देखा जो कहता है कि यह बहुत तेज़ है (इसलिए मुझे विश्वास नहीं है ...) मैं इसे देखकर देखूंगा, मुझे जाना है। फिर भी धन्यवाद। (यह अन्य विषय की नकल नहीं कर रहा है, धीमी गति से जवाब वहाँ थे) – Ohad

एक भयानक लेख है, +1 –

देखते हैं एल्गोरिदम बहुत बहुत तेजी से इस सरल एक से, एक प्रमुख के लिए मेरा उत्तर –

कई टिप्पणियां।

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

स्रोत

2010-09-28 03:39:23 John

परीक्षण को देखने के इस तरह के एक बोर है, कि मैं पूरी तरह से jlv के साथ सहमत हैं ... बस स्टोर और इसे देखो। वास्तव में, एक वैश्विक वैश्विक webservice होना चाहिए जो विश्व स्तर पर कैश किया गया हो, जो उत्तर प्रदान कर सकता है ... या बेहतर अभी भी, जावा को सभी प्राइम्स को लुकअप में अधिकतम int में स्टोर करना चाहिए; डॉकर दुनिया में एक ऐसी छवि के साथ एक छवि होनी चाहिए जो लुकअप सहित प्राइम्स के आसपास कई प्रकार की सेवाएं प्रदान करे। इसका परीक्षण करने के लिए बस इतना ही बोर है, और उसके बाद अपनी पसंद की भाषा में सबसे अधिक प्रदर्शन विधि की तलाश करें। – Beezer

आप Sieve of Atkin का उपयोग कर उस से बेहतर कर सकते हैं (जो तेजी से कुछ मिल रहा है), लेकिन यह और सही ढंग से यह तेजी से लागू करने के लिए काफी मुश्किल है। विकिपीडिया छद्म कोड का एक सरल अनुवाद शायद पर्याप्त नहीं है।

स्रोत

2010-09-28 12:06:54 Landei

हां, मैं Atkins की चलनी ... मेरी सरणी भी निहित भी संख्या करने की कोशिश की लेकिन मैं उन्हें छू नहीं था ... यह 1.5 गुना धीमी गति से eroathenes चलनी थी। (मुझे मिले अधिकांश कोड मेरे युग से दोगुना हो गए थे)। और निश्चित रूप से - मैं भी गुण primes और मान लीजिए कि मैं अनुकूलन करने के लिए पता है ... लेकिन यह अभी भी धीमी (मेरे सरणी में unsused बाइट्स ... कि कोई फर्क नहीं करना चाहिए रहे हैं) है इस्तेमाल किया। – Ohad

आपको यह कोड क्यों नहीं दिखाया जाता है? – Landei

कागज के लेखकों में से एक से एक बहुत तेजी से सी कार्यान्वयन जो उसका वर्णन http://cr.yp.to/primegen.html पर है – Olathe

अब तक मेरे अनुभव में सबसे तेज़ एल्गोरिदम 2, 3 और 5 के लिए व्हील कारक के साथ एराथोस्टेनेस की चलनी है, जहां शेष संख्याओं के बीच प्राइम बाइट सरणी में बिट्स के रूप में दर्शाए जाते हैं। जावा में मेरे 3 साल पुराने लैपटॉप के एक कोर पर 1 अरब तक की कीमतों की गणना करने में 23 सेकंड लगते हैं।

पहिया कारक के साथ एटकिन की चाकू दो धीमी गति के कारक के बारे में थी, जबकि सामान्य BitSet के साथ यह लगभग 30% तेज था।

this answer भी देखें।

स्रोत

2010-10-28 12:39:00 starblue

मैंने एक एल्गोरिदम किया जो सी में लिखे गए 350 एम-नोटबुक पर 0.65 सेकंड के लिए 2-90 000 000 की सीमा से प्राइम नंबर प्राप्त कर सकता है .... आपको बिटवाई ऑपरेशंस का उपयोग करना होगा और इंडेक्स को पुन: गणना करने के लिए "कोड" होना होगा अपनी सरणी के कंक्रीट बिट की अनुक्रमणिका के लिए आप चाहते हैं। उदाहरण के लिए यदि आप संख्या 2 के गुना चाहते हैं, तो कंक्रीट बिट्स उदाहरण के लिए होंगे .... 10101000 ... इसलिए यदि आप बाएं से पढ़ते हैं ... आपको इंडेक्स 4,6,8 मिल जाता है ... यह

स्रोत

2011-03-22 09:50:21 DarkEye

प्राइम नंबर खोजने के लिए फास्ट एल्गोरिदम?

उत्तर

संबंधित मुद्दे