मैं वर्तमान में निम्न कोड लेकिन इसकी बड़ी संख्यामैं एक इष्टतम एल्गोरिथ्म की जरूरत है सी में अधिमानतः एक नंबर एन ++ या सी #
static int divisor(int number)
{
int i;
for (i = number/2; i >= 1; i--)
{
if (number % i == 0)
{
break;
}
}
return i;
}
पहले सोचा था कि आप पा सकते हैं के लिए बहुत धीमी गति से उपयोग कर रहा हूँ में से सबसे बड़ी भाजक को खोजने के लिए सबसे छोटा divisor डी (निश्चित रूप से 1 के बराबर नहीं), तो एन/डी सबसे बड़ा divisor होगा जिसे आप ढूंढ रहे हैं।
उदाहरण के लिए यदि एन 3 से विभाजित है तो आपको जवाब खोजने के लिए 2 पुनरावृत्तियों की आवश्यकता होगी - आपके मामले में यह एन/6 पुनरावृत्तियों के बारे में होगा।
संपादित करें: आगे अपने एल्गोरिथ्म सुधार करने के लिए आप, (जाँच के बाद अगर आप संख्या सम है) केवल विषम संख्या के माध्यम से पुनरावृति कर सकते हैं या और भी बेहतर अगर आप अभाज्य संख्या की सूची है पूर्व गणना की तो आप उन के माध्यम से पुनरावृति कर सकते हैं केवल इसलिए कि सबसे छोटा divisor स्पष्ट रूप से एक प्रमुख संख्या है।
इसमें पहले "सबसे अधिक संभावना" divisors की जांच का अतिरिक्त लाभ है। (यानी 2 9 8 9) – Justin
@Vladimir की तुलना में मनमाने ढंग से एक divisor होने की "अधिक संभावना" है: यह एक छिपे हुए दावे है कि छोटे divisors अधिक घने हैं (औसतन, सभी संख्याओं के लिए), यानी यह खोजने के लिए तेज़ है एन/2 से नीचे की ओर से 2 से ऊपर एक divisor शुरू होता है। हालांकि यह सहजता से उचित लगता है, क्या आपके पास इसका समर्थन करने के लिए कुछ गणित हैं? – davka
और वास्तव में, यदि कोई ऐसा फ़ंक्शन है जो उचित संख्या की प्राइम की गणना करता है (या केवल प्राइम्स की एक तालिका बनाते हैं), और यह पता लगाना कि इनमें से कौन सा सभी के माध्यम से फिर से शुरू करने की बजाय संख्या को विभाजित करता है विषम संख्या। – supercheetah
अपनी खोज स्थान को सीमित करने के लिए, आपको 2 से शुरू होना चाहिए और संख्या के वर्ग रूट पर काम करना चाहिए। 27 से 2 तक विभाजित होने वाली बहुत अधिक संख्याएं (एक सीमित खोज स्थान में) हैं, इसलिए आपको उच्चतम, सांख्यिकीय रूप से बोलने से कम विभाजक होने की अधिक संभावना है।
जब आप प्रसंस्करण (उदाहरण के लिए) 1,000,000 प्रसंस्करण करते हैं, तो आपको आधे मूल्य के बजाय वर्ग रूट का उपयोग करते समय एक बड़ा अंतर मिलेगा। अंतर आपकी विधि के लिए 500,000 की खोज स्थान के बीच है और वर्ग रूट विधि के लिए 1,000 काफी है।
एक और लाभ दो के गुणकों को छूट देकर सामने की जगह पर खोज स्थान को कम करना है। फिर, जब आपके पास सबसे कम विभाजक होता है, तो सबसे अधिक केवल उस संख्या से विभाजित होता है।
स्यूडोकोड:
if n % 2 == 0: # Halve search space straight up.
print n/2
else:
i = 3 # Start at 3.
while i * i <= n: # Or use i <= sqrt(n), provided sqrt is calc'ed once
if n % i == 0:
print n/i # If multiple, get opposite number, print and stop
break
i = i + 2 # Only need to process odd numbers
मान लीजिए कि संख्या 10^9 थी, क्या मेरी विधि को सबसे बड़ा divisor तेज़ी से नहीं मिलेगा i.e 5 * (10^8)? – Ronzii
@ रोन्ज़ी। 10^9 नंबर तुरंत इस कोड द्वारा पकड़ा जाएगा क्योंकि यह दो से विभाजित है। मैं दूसरे कथन में 10^9/2 (5x10^8) वापस कर दूंगा। यही कारण है कि आप कम शुरू करते हैं, न कि एन/2 पर। कम कारकों को खोजने की संभावना बहुत बेहतर है। – paxdiablo
अच्छी सलाह। मैं इसे वास्तव में जल्दी से खोजने में सक्षम था! – Ronzii
अगर यह इष्टतम समाधान है पता नहीं है, लेकिन आप शायद 2 तब के रूप में ऊपर की तरफ इस तरह जा रहा में बेहतर शुरू होगा:
static int divisor(int number)
{
int i;
for (i = 2; i <sqrt(number); i++)
{
if (number % i == 0)
{
break;
}
}
return number/i;
}
इसे प्राइम के साथ काम करने के लिए भी:
static int divisor(int number)
{
int i;
for (i = 2; i <=sqrt(number); i++)
{
if (number % i == 0)
{
return number/i;
}
}
return 1;
}
@ बुनीट: उपरोक्त कोड सही परिणाम नहीं देगा – bjskishore123
इस बात की शर्तों के तहत @bjsk, _specify_ को न भूलें, यह किस स्थिति में काम नहीं करता है। – paxdiablo
@ bjskishore123: हाँ वापसी का मूल्य गलत है यदि संख्या एक प्राइम है लेकिन इसे आसानी से til sqrt (संख्या) +1 की जांच करके ठीक किया जा सकता है, फिर लौटने पर उस मान की जांच कर रहा है, या ब्रेक कहां और बाहर के बाहर लौट रहा है (अगर यह एक प्रमुख है)। मैंने इसे एक त्वरित उदाहरण के रूप में लिखा है। –
अनुकूलन: एक विषम संख्या में सबसे बड़ा विभाजक के रूप में भी संख्या नहीं हो सकती है। इस फ़िल्टर का उपयोग जल्दी नंबर पर करें। तो यदि विषम संख्या दी जाती है।
सबसे पहले तो पाश
इस विषम संख्या के लिए गति में सुधार होगा में 2 हर द्वारा मैं घटती साथ 2.
प्रभाग है।
इसके अलावा संख्याओं का सबसे बड़ा वास्तविक विभाजक स्वयं का आधा हिस्सा है। – Calmarius
एक विशाल अनुकूलन (सुनिश्चित नहीं है कि यह पूरी तरह से इष्टतम है - आपको इसके लिए गणितज्ञ से पूछना होगा) केवल प्रमुख संख्याओं का उपयोग करके ऊपर की ओर खोजना है। व्लादिमीर और बनीट ने कहा, ऊपर की ओर खोजना बेहतर है, क्योंकि आप इसे बहुत तेज़ पाएंगे। फिर, उलटा (number/i) वापस करें। हालांकि, अगर आप पहले से ही 2 कोशिश कर चुके हैं और सूखे आते हैं, तो 4 या 6 की कोशिश करने में कोई बात नहीं है। इसी प्रकार, यदि आपने 3 की कोशिश की है, तो 6 या 9 की कोशिश करने में कोई बात नहीं है।
तो, यदि चलने का समय एक बड़ी चिंता है, तो आपके प्रोग्राम में हार्ड कोड किए गए पहले 100 प्राइम्स की एक सूची हो सकती है। उनमें से प्रत्येक का परीक्षण करें। यदि आपको तब तक कोई जवाब नहीं मिलता है, तो आप केवल 2 (संख्याओं को छोड़कर) बढ़ा सकते हैं।
आपने मूल रूप से "बड़ी संख्याओं के कारक" समस्या को मारा है, जो आज की सार्वजनिक कुंजी एन्क्रिप्शन का आधार है और एक कम्प्यूटेशनल हार्ड समस्या होने के लिए जाना जाता है (या उम्मीद है)। मुझे उम्मीद है कि आपको एक बेहतर समाधान नहीं मिलेगा, अन्यथा दुनिया का पूरा सुरक्षा बुनियादी ढांचा गिर जाएगा ... :)
हां, ओपी बड़ी संख्या में फैक्टरिंग की धीमी गति से निपट रहा है, लेकिन आरएसए और डीएसए जैसे सार्वजनिक कुंजी क्रिप्टोग्राफिक सिस्टमों में उपयोग की जाने वाली संख्याओं को फैक्टर करने के बराबर कहीं भी स्केल पर नहीं है। – mctylr
बड़ी संख्या के कारकों को खोजने के लिए उद्योग मानक तरीकों में से एक क्वाड्रैटिक सिलाई एल्गोरिदम है।
http://en.wikipedia.org/wiki/Quadratic_sieve
पी.एस.:
इस का एक पढ़ा है आपको यह भी विचार करना चाहिए कि आपकी संख्या कितनी बड़ी है। विभिन्न कारक एल्गोरिदम एक निश्चित आकार के लिए अच्छा प्रदर्शन करते हैं, न कि दूसरों के लिए। जैसा कि क्यूएस विकी आलेख में उल्लेख किया गया है, यह विधि आमतौर पर लगभग 100 दशमलव अंकों से कम संख्या के लिए सबसे तेज़ है। http://programmingpraxis.com/contents/themes/#Prime%20Numbers
प्रोग्रामिंग अभ्यास नियमित रूप से प्रोग्रामिंग चुनौतियों सेट लोग एक शुक्रवार खाने पर मज़ा का एक सा के लिए हल करने के लिए के लिए: -
यहाँ एक नज़र डालें। यह विशेष समस्या बहुत अधिक है और कोड के साथ सचित्र इसे हल करने के लिए कई प्रसिद्ध एल्गोरिदम हैं।
कुछ अतिरिक्त अनुकूलन:
1. If even then divisable by 2.
2. If the sum of the digits is divisable by 3, then number is divisble by 3 (ie 78 = 7 + 8 = 15 = 1 + 5 = 6 which is divisable by 3)
3. If it ends in 0 or 5 it is divisable by 5
गॉर्डन।
सर्वश्रेष्ठ एल्गोरिदम इस बात पर निर्भर करेगा कि आपकी संख्या वास्तव में कितनी बड़ी होगी।
यह समस्या मूल रूप से फैक्टरिंग पूर्णांक के रूप में कठिन है - यदि कुछ फैक्टरिंग एल्गोरिदम है, तो इसे सबसे बड़ा गैर-तुच्छ विभाजक बनाने के लिए इसका उपयोग करना आसान होगा। फिर, आप किसी भी संख्या के लिए नियोजित सभी ज्ञात फैक्टरिंग एल्गोरिदमों को अपनी 'गड़बड़ी' पर निर्भर करते हैं, क्योंकि विभिन्न फैंसी के लिए इन फैंसी एल्गोरिदम के अलग-अलग प्रदर्शन होंगे।
आपको शायद क्रिप्टोग्राफी, एल्गोरिदमिक्स और कम्प्यूटेशनल नंबर सिद्धांत पर अच्छी किताबों में आपके प्रश्न के कई (शायद अलग) उत्तर मिलेंगे।
फिर से, आपके पैमाने के आधार पर, यह एक बड़ी सूची को बड़ी संख्या में एक प्रमुख सूची को सहेजने का विकल्प भी हो सकता है, इसे सहेज सकता है, और फिर सबसे छोटी विभाजक के लिए इस सूची में इनपुट नंबर खोज दिया जा सकता है - जो तुरंत होगा सबसे बड़ा divisor भी पॉप अप।
पहला प्राइम ढूंढें जो संख्या एन को विभाजित करता है। मान लीजिए कि प्राइम पी है। डी द्वारा विभाजित डी। यह आवश्यक परिणाम है जो आप चाहते हैं।
एन स्वयं एन के सबसे बड़े विभाजक नहीं होंगे? शायद "वापसी संख्या;" क्या समारोह है, आप ढूंढ रहे हैं? – SadSido
एन का सबसे बड़ा विभाजक एन स्वयं है ... – Vladimir
पहला सुधार: 'संख्या/2' पर शुरू न करें, लेकिन' sqrt (संख्या) 'पर शुरू करें। – phimuemue