मैंने प्रोजेक्ट यूलर के लिए 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);;
    }

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

0
udbhavs 8 फरवरी 2017, 18:31
 – 
assylias
8 फरवरी 2017, 18:34
4
पूर्णांक अतिप्रवाह। मुझे संदेह है target * i अतिप्रवाह।
 – 
Boris the Spider
8 फरवरी 2017, 18:34
यह किस लाइन पर दुर्घटनाग्रस्त हो जाता है? क्या आपने अपना कोड डीबग करने का प्रयास किया है?
 – 
luk2302
8 फरवरी 2017, 18:34
यह भी ध्यान रखें कि इस for (int i = target;; i ++) { if (target*i >= primes.length ) { break; } ... } को for (int i = target; target*i < primes.length; i ++) { ... } से बदला जा सकता है
 – 
assylias
8 फरवरी 2017, 18:36
46349 * 46349 = 2,148,229,801 और अधिकतम समर्थित int 2,147,483,647 है, जो समाप्त हो जाता है और ऋणात्मक संख्या बन जाता है।
 – 
Compass
8 फरवरी 2017, 18:47

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
RealSkeptic 8 फरवरी 2017, 18:53

आपको primes सरणी में समस्या है।

सबसे पहले, त्रुटि को पढ़कर, आपकी सरणी स्पष्ट रूप से आपके तर्क के लिए पर्याप्त 'लंबी' नहीं है, क्योंकि आप इसे boolean[] primes = new boolean[2000001]; के रूप में परिभाषित करते हैं और आपके पास -2146737495 का ArrayIndexOutOfBoundsException है।

इसलिए i, target और cycles वेरिएबल के लिए int के बजाय long या BigInteger का उपयोग करने का प्रयास करें। फिर भी, आपको अपने तर्क के बारे में पुनर्विचार करना होगा क्योंकि समस्या अपने आप में अतिप्रवाह नहीं है, बल्कि वह सरणी है जो काफी लंबी नहीं है।

0
JFPicard 8 फरवरी 2017, 18:43
सरणी काफी लंबी है। यह सुनिश्चित करने के लिए कि आप सरणी से बाहर नहीं जाते हैं, चेक दोषपूर्ण है।
 – 
RealSkeptic
8 फरवरी 2017, 18:45
तर्क दोषपूर्ण आईएमएचओ है, इसलिए मुझे लगता है कि समाधान यह जांच नहीं कर रहा है कि सूचकांक सरणी से बाहर है, लेकिन बड़े प्राइम को खोजने के तरीके को बदलने के लिए।
 – 
JFPicard
8 फरवरी 2017, 18:55