मैंने प्रोजेक्ट यूलर के लिए n तक के प्राइम्स के योग की गणना करने के लिए एरास्टोथेनीज प्रोग्राम की एक साधारण चलनी बनाई। यह 100, 1,000, 10,000 आदि के लिए ठीक काम करता है लेकिन जब मैं 1 या 2 मिलियन करता हूं, तो यह मुझे यह देता है:
Java.lang.ArrayIndexOutOfBoundsException: -2146737495
यह छोटी संख्या के लिए नहीं होता है, मैं बूलियन सरणी का उपयोग करता हूं।
boolean[] primes = new boolean[2000001];
ArrayList<Integer> list = new ArrayList<Integer>();
for (int i = 2; i < primes.length; i++){
primes[i] = true;
}
boolean stop = false;
int target = 2;
int cycles = 1;
while (!stop) {
list.add(target);
for (int i = target;; i ++) //
{
if (target*i >= primes.length ) {//
break;
}
primes[target*i] = false;//
}
for (int i = target + 1; ; i ++) {
if(i >= primes.length) {
stop = true;
break;
}
else if (primes[i]) {
target = i;
break;
}
}
cycles ++;
}
int sum = 0;
for (int i = 0; i < list.size(); i++) {
sum += list.get(i);;
}
मेरा लक्ष्य वास्तव में उत्तर खोजना नहीं है, लेकिन कई बार मैंने इस प्रकार की त्रुटियों के कारण अपना कोड छोड़ दिया है। मैं उनके लिए एक स्रोत खोजना चाहता हूं।
3 जवाब
आपके पास एक दोषपूर्ण चेक है जो पूर्णांक ओवरफ़्लो को ध्यान में नहीं रखता है।
for (int i = target;; i ++) //
{
if (target*i >= primes.length ) {// This is the check
break;
}
primes[target*i] = false;// Here is where it overflows
}
एक बार जब आप एक i हिट करते हैं जो target * i को एक पूर्णांक से बड़ा बना सकता है, तो पूर्णांक ओवरफ्लो हो जाता है। यानी अब यह निगेटिव हो जाएगा। और निश्चित रूप से, एक ऋणात्मक संख्या के लिए, target*i >= primes.length गलत होगा।
और निश्चित रूप से, एक ऋणात्मक संख्या किसी सरणी में अनुक्रमणिका नहीं हो सकती है। इसे ब्रेक पर रुक जाना चाहिए था, लेकिन ऐसा नहीं हुआ क्योंकि शर्त पूरी नहीं हुई थी।
आपको जो करना चाहिए वह अधिकतम i की गणना है जिसकी अनुमति है, और इसे लूप की स्थिति के रूप में रखें:
int maxI = primes.length / target;
for (int i = target; i < maxI; i ++) //
{
primes[target*i] = false;// Here is where it overflows
}
maxI वह अधिकतम संख्या है जिसे आप target से गुणा कर सकते हैं और फिर भी primes.length तक नहीं पहुंच सकते। अब आपको अपने चेक की आवश्यकता नहीं है (क्योंकि target को i से गुणा करने पर कभी भी primes.length से बड़ी संख्या प्राप्त नहीं होगी। और यह कभी भी ओवरफ्लो नहीं होगा, क्योंकि गुणा हमेशा एक संख्या देता है। यह सरणी के आकार से कम है, इसलिए Integer.MAX_VALUE से कम है।
एक और, कम खर्चीला (कम गुणा) विधि होगी:
if ( primes.length / target >= target ) {
for (int i = target * target; i < primes.length; i += target ) //
{
primes[i] = false;
}
}
if में चेक अतिप्रवाह से बचने के लिए आवश्यक है, यदि आपके पास बहुत बड़ा target है।
ऐसा इसलिए है क्योंकि आप एक इंट का उपयोग कर रहे हैं, जिसकी ऊपरी सीमा 2^31-1 है: देखें https ://en.wikibooks.org/wiki/Java_Programming/Primitive_Types
बड़ी संख्या को संभालने के लिए, आपको BigInteger वर्ग।
आपको primes सरणी में समस्या है।
सबसे पहले, त्रुटि को पढ़कर, आपकी सरणी स्पष्ट रूप से आपके तर्क के लिए पर्याप्त 'लंबी' नहीं है, क्योंकि आप इसे boolean[] primes = new boolean[2000001]; के रूप में परिभाषित करते हैं और आपके पास -2146737495 का ArrayIndexOutOfBoundsException है।
इसलिए i, target और cycles वेरिएबल के लिए int के बजाय long या BigInteger का उपयोग करने का प्रयास करें। फिर भी, आपको अपने तर्क के बारे में पुनर्विचार करना होगा क्योंकि समस्या अपने आप में अतिप्रवाह नहीं है, बल्कि वह सरणी है जो काफी लंबी नहीं है।
संबंधित सवाल
नए सवाल
java
जावा एक उच्च स्तरीय प्रोग्रामिंग भाषा है। इस टैग का उपयोग तब करें जब आपको भाषा का उपयोग करने या समझने में समस्या हो। इस टैग का उपयोग शायद ही कभी किया जाता है और इसका उपयोग अक्सर [वसंत], [वसंत-बूट], [जकार्ता-ई], [Android], [javafx], [हडूप], [श्रेणी] और [मावेन] के साथ किया जाता है।
target * iअतिप्रवाह।for (int i = target;; i ++) { if (target*i >= primes.length ) { break; } ... }कोfor (int i = target; target*i < primes.length; i ++) { ... }से बदला जा सकता हैint2,147,483,647 है, जो समाप्त हो जाता है और ऋणात्मक संख्या बन जाता है।