هذا هو رئيس الوزراء مولد فعالة C ++؟

Question

هل هذا ينظر إليها على أنها في كفاءة المولدات عدد أولي. ويبدو لي أن هذا هو فعال جدا. هو استخدام للتيار الذي يجعل برنامج تشغيل أبطأ؟

واني اسعى الى تقديم هذا SPOJ ويقول لي هذا الحد وقتي تجاوز ...

#include <iostream>
#include <sstream>

using namespace std;

int main() {
    int testCases, first, second, counter = 0;
    bool isPrime = true;
    stringstream out;

    cin >> testCases;

    for (int i = 0; i < testCases; i++) {
        // get the next two numbers
        cin >> first >> second;

        if (first%2 == 0)
            first++;

        // find the prime numbers between the two given numbers
        for (int j = first; j <= second; j+=2) {
            // go through and check if j is prime
            for (int k = 2; k < j; k++) {
                if (j%k == 0) {
                    isPrime = false;
                    break;
                }
            }
            if (isPrime) {
                out << j << "\n";
            }
            isPrime = true;
        }
        out << "\n";
    }

    cout << out.str();

    return 0;
}

وتحرير: يفترض هذا البرنامج لتوليد الأعداد الأولية بين الأرقام المحددة في الإدخال. (انظر هنا لمزيد من التفاصيل: رئيس مولد مشكلة )

و-Tomek

Answer 1

وهذا هو خطوة واحدة (تخطي حتى أرقام) أعلاه خوارزمية ساذجة. أود أن أقترح المنخل من إراتوستينس كما خوارزمية أكثر فعالية. من الرابط أعلاه:

<اقتباس فقرة>   

وتعقيد الخوارزمية   O ((nlogn) (loglogn)) مع ذاكرة   شرط O (ن). ومجزأة   نسخة من منخل من إراتوستينس،   مع تحسينات أساسية مثل عجلة   التعميل، يستخدم O عمليات (ن)   وO (N1 / 2loglogn / logn) أجزاء من   الذاكرة.

والخوارزمية كنت تعطي في مكان ما بالقرب O (ن ^ 2). لتسريع تحصل من خلال تخطي يسوي ليست كبيرة لأنك سوف تجد عددا حتى لا يكون رئيس في أول اختبار له. غربال لديه متطلبات أكبر بكثير الذاكرة، ولكن تعقيد وقت التشغيل هو أعلى بكثير لكبير <م> N .

Answer 2

وأنت تبحث عن الكثير المزيد من الأرقام من لديك - على الأكثر ما عليك سوى الذهاب إلى <= (sqrt(num))

Answer 3

وإليك المنخل بسيط من إراتوستينس. أنها لا تتطلب predeclaring مجموعة منطقية كبيرة، لكنه ما زال >> O (ن) في الزمان والمكان. طالما لديك ذاكرة كافية، على الرغم من أنه يجب أن يكون أسرع بشكل ملحوظ مما أسلوب ساذج الحالي الخاص بك.

#include <iostream>
#include <map>

using namespace std;

template<typename T = int, typename M = map<T, T> >
class prime_iterator {
    public:
        prime_iterator() : current(2), skips() { skips[4] = 2; }
        T operator*() { return current; }
        prime_iterator &operator++() {
            typename M::iterator i;
            while ((i = skips.find(++current)) != skips.end()) {
                T skip = i->second, next = current + skip;
                skips.erase(i);
                for (typename M::iterator j = skips.find(next);
                        j != skips.end(); j = skips.find(next += skip)) {}
                skips[next] = skip;
            }
            skips[current * current] = current;
            return *this;
        }
    private:
        T current;
        M skips;
};

int main() {
    prime_iterator<int> primes;
    for (; *primes < 1000; ++primes)
        cout << *primes << endl;
    return 0;
}

إذا هذا لا يزال بطيئا جدا بالنسبة لك، قد ترغب في متابعة غربال أتكين ، والمنخل الأمثل من إراتوستينس.

في الواقع، هذه ليست سوى كفاءة نسبيا إذا كانت مجموعة من الأعداد الأولية لتوليد يبدأ منخفضة. إذا كانت ملزمة أقل بالفعل إلى حد كبير والحد الأعلى هو ليس أكبر بكثير من الأسفل، ثم الطرق النخل والعمل الإسراف وتريد ان تكون أفضل حالا تشغيل <لأ href = "http://en.wikipedia.org / ويكي / Primality_test "يختلط =" نوفولو noreferrer "> اختبار بريماليتي .

Answer 4

وأكثر شيء واحد، لا تستخدم الجذر التربيعي (ن) في حلقة:

for(int k=1;k<sqrt(n);++k)

إذا لم يكن هناك الأمثل جيد، وسيتم احتساب الجذر التربيعي في كل التكرار.

استخدم

for (int k=1;k*k < n;++k)

وأو ببساطة

int sq = sqrt ( n );
for (int k=1;k<sq;++k)

Answer 5

ويمكن ان يكون أكثر قليلا فعالة. لا تحتاج لبدء ك في 2، كنت صنع بالفعل تأكد من عدم اختبار حتى الأرقام. حتى يبدأ ك في 3.
ثم زيادة ك بنسبة 2 في كل مرة لأنك لا تحتاج إلى اختبار الأرقام حتى غيرها. أنجع وسيلة أستطيع أن أفكر في أن الاختبار الوحيد إذا كان العدد يقبل القسمة على الأعداد الأولية المعروفة (ثم عندما تجد واحد آخر إضافة ذلك إلى القائمة يمكنك اختبار مع).

Answer 6

for (int k = 2; k < j; k++) {
     if (j%k == 0) {
         isPrime = false;
         break;
     }
}

ويجب أن تكون:

for(int k = 3; k <= j/2; k+=2 )
{
  if( j % k == 0 )
      break;
}

ي / 2 حقا يجب أن الجذر التربيعي (ي) ولكنه عادة ما يكون تقدير جيد بما فيه الكفاية.