मैं पहले 500 अभाज्य संख्याओं की गणना करने के लिए एराटोस्थनीज की छलनी का उपयोग कर रहा हूं। प्रोग्राम क्या करता है n % p जहां n उपयोगकर्ता इनपुट है और p 2 और sqrt(n) के बीच है।

मैं केस n = 2297 के लिए अपने प्रोग्राम का परीक्षण कर रहा हूं, जो एक प्राइम है। मेरा प्रोग्राम क्यों कहता है कि यह समग्र है?

bool primalityTestSieve(int n){
    if(n == 2) return true; //tiny complication due to ceil(sqrt(2))

    //Sieve with first MAX
    bool arr[MAX - 1];
    int i, j, s = ceil(sqrt(n));
    for(i = 2; i < MAX; i++){
        arr[i - 2] = true;          //fill arr[] with true
    }
    for(i = 2; i < (int) sqrt(MAX); i++){
        if(arr[i - 2]){
            for(j = i*i; j < MAX; j+= i)
                arr[j - 2] = false;
        }
    }

    //Array storing the primes
    int primes[MAX];
    j = 0;  //Counter for the index of the primes
    for(i = 0; i < MAX; i++)
        if(arr[i]){
            primes[j] = i + 2;
            j++;
        }

    //Prime test, first using sieve
    for(i = 0; primes[i] <= s; i++)
        if(n % primes[i] == 0) return false;

    //Naive prime test for larger divisors
    for (i = primes[j]; i <= s/2; i++)
            if(((n % 2) == 0)||((n % (2*i + 1)) == 0))  return false;
    return true;
}

ध्यान दें कि MAX एक पैरामीटरयुक्त मैक्रो है और 500 के बराबर है।

-1
Luke Collins 21 मई 2016, 07:29
MAX का मान क्या है? for(i = 0; i < MAX; i++) के बाद j का मान क्या है?
 – 
chux - Reinstate Monica
21 मई 2016, 07:35
मैंने पोस्ट को MAX के संदर्भ में अपडेट किया। j का मान primes[] में अंतिम तत्व का पता है।
 – 
Luke Collins
21 मई 2016, 07:37
1
//fill arr[] with true ऐसा नहीं है
 – 
chux - Reinstate Monica
21 मई 2016, 07:37
1
मुझे लगता है कि डिबगिंग यहाँ समाधान है ...
 – 
Oliver Charlesworth
21 मई 2016, 07:44
2
j का मान primes में अंतिम तत्व का पता है [] j अंतिम elemnet अगला अनुक्रमणिका है।
 – 
BLUEPIXY
21 मई 2016, 07:46

1 उत्तर

सबसे बढ़िया उत्तर

आपका कोड चलनी का उपयोग 2 और 500 के बीच के अभाज्य संख्याओं को खोजने के लिए करता है। (जैसा कि आप अपने पाठ में कहते प्रतीत होते हैं, पहले 500 अभाज्य नहीं)।

फिर आप उन प्राइम्स को primes[] एरे में j के साथ कॉपी करते हैं, जैसे कि ऐरे में कितने आइटम हैं। तो इस बिंदु पर primes[] में कुछ संख्याएं 500 से कम हैं और उसके बाद जंक का एक गुच्छा है।

फिर आपके पास कोड है:

for(i = 0; primes[i] <= s; i++)

s, n == 2297 के लिए 48 होगा। यह लूप तब n को 48 तक किसी भी अभाज्य संख्या से विभाज्य होने की जांच करेगा, जो विफल हो जाएगा। (इस लूप में एक शर्त के रूप में i < j भी होना चाहिए ताकि यदि आप एक बड़ा n दर्ज करते हैं तो यह कबाड़ में नहीं पढ़ता है)।

हालाँकि आप तब लिखते हैं:

for (i = primes[j]; i <= s/2; i++)

याद रखें कि j में वर्तमान में अभाज्य संख्या है, और अभाज्य संख्या primes[0] से primes[j-1] तक है। इसका मतलब है कि primes[j] एक जंक वैल्यू है; इसलिए आपने i को अपरिभाषित व्यवहार के कारण रद्दी पर सेट कर दिया है।

(मुझे यकीन नहीं है कि आप वास्तव में उस आखिरी लूप में क्या करने की कोशिश कर रहे थे, यह स्पष्ट नहीं है कि आप कहां से शुरू करना और खत्म करना चाहते हैं, या आप n%2 प्रत्येक लूप पुनरावृत्ति आदि का परीक्षण क्यों करते हैं - यदि आप वर्णन कर सकते हैं कि आप क्या कर सकते हैं वहां करने की कोशिश कर रहे हैं तो मैं कुछ कोड सुझाऊंगा)।

1
M.M 21 मई 2016, 08:05
आपके जवाब के लिए धन्यवाद। मैं समस्या को ठीक करने में कामयाब रहा, जैसा कि आपने ठीक ही कहा था कि यह जंक एलिमेंट primes[j] को अंतिम फॉर-लूप में पास कर रहा था। अंतिम लूप के संबंध में - यदि इनपुट की गई संख्या का वर्गमूल> MAX है, तो चलनी द्वारा उत्पन्न संख्याएं प्रारंभिकता की जांच के लिए पर्याप्त नहीं हैं। मैं परीक्षण करना चाहता हूं कि क्या सभी विषम संख्याओं के लिए n % p = 0 p चलनी द्वारा उत्पन्न अंतिम अभाज्य और इनपुट के वर्गमूल के बीच। क्या यह सही ढंग से किया जाता है?
 – 
Luke Collins
21 मई 2016, 17:22