• 0
محمد علاء الدين

طلب شرح الغربلة المجزئه لـ Eratosthenes

سؤال

السلام عليكم و رحمة الله

 

الموضوع هو طلب شرح Segmented Sieve of Eratosthenes، قرأت مواضيع عديده و أكواد كثيرة لها و لكن حتى الأن لا أستطيع فهمها؟!!

 

إن استطاع أحد أن يضع شرح لها هنــا - مع مثال بسيط إن كان بالإمكان - فجزاه الله خيرا.

 

 

و الله ولي التوفيق

تم تعديل بواسطه C++er
1

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه

1 إجابات على هذا السؤال .

  • 0

السلام عليكم ورحمة الله وبركاته

أولاً أعتذر للتأخر الكبير في الرد , وربما تكون المشكلة قد حُلّت , وأرجو أن يكون هناك أي فائدة فيما سأكتبه

الكود التالي مشروح سطراً بسطر , وفيه 2 مستويات تتبع حسب الثوابت البوليانية في البداية

أرجو أن يكون الكود واضح ومفهوم

//SEGMENTED SIEVE OF ERATOTHENES//Produced by : mostafa 36a2//as a special gift to Mr.C++er//arabteam2000.com#include <iostream>#include <bitset>#include <vector>using namespace std;int main(){    const bool ENABLE_SEGMENT_OUTPUT   =false;//if you want to watch the progress of segments    const bool ENABLE_NEW_PRIMES_OUTPUT=true ;//if you want to watch the progress of saving new primes only    const bool ENABLE_OUTPUT           =false;//if you want to watch all the progress    typedef unsigned long long int ulli;//use long long to avoid overflow[actually we don't need it]    const ulli MAX_NUMBER_TO_SIEVE  =100;//try 10^9 :)    /*there is only 2 limits on MAX_NUMBER_TO_SIEVE :    1- sqrt(MAX_LONG_LONG)[because of overflow]    2- size of the vector that saving the primes    */    const ulli SEGMENT_SIZE         =5;//the minimum Size is 2,the maximum depend on size of bitset    const ulli NUMBER_OF_SEGMENTS   =MAX_NUMBER_TO_SIEVE/SEGMENT_SIZE;    vector<ulli>primes;//vector to save primes    /*remember that vector is bad when stretching ,make the whole thing slow      you can use linked-list or array of max_number_of_primes < 1000000000    */    vector<ulli>offset;//vector to save how far is the first multiple of the prime from the start of the segment    bitset<SEGMENT_SIZE>p;//only few bits could be used to sieve all primes    //step 1: start with seiving primes < SEGMENT_SIZE    p.set();    p.set(0,0);    p.set(1,0);    for(int i=2;i<SEGMENT_SIZE;i++)        if(p.test(i))            {                primes.push_back(i);                int j;                for(j=i*i;j<SEGMENT_SIZE;j+=i)//j=i*i may cause overflow[not really]                    p.set(j,0);                offset.push_back(j-SEGMENT_SIZE);            }        for(int i=0;i<primes.size();i++)        {            if(ENABLE_NEW_PRIMES_OUTPUT|ENABLE_OUTPUT)                cout<<"base prime "<<primes.at(i);            if(ENABLE_OUTPUT)                cout<<" offset "<<offset.at(i);            if(ENABLE_NEW_PRIMES_OUTPUT|ENABLE_OUTPUT)                cout<<endl;        }    if(ENABLE_SEGMENT_OUTPUT)        cout<<"Base segment is ready"<<endl;    //End step 1;and segment 0 is ready    //step 2:repeate sieve for all segments    for(ulli segment=1;segment<NUMBER_OF_SEGMENTS;segment++)//every segment is SEGMENT_SIZE number        {            if(ENABLE_SEGMENT_OUTPUT)                cout<<"----- segment "<<segment<<" -----"<<endl;            p.set();//all ones , assume that they are primes            for(ulli index=0; index<primes.size();index++)/*for all primes inside vector(primes)                [could be improved:                    we don't have to sieve on the primes > sqrt(MAX_NUMBER_TO_SIEVE)                    and also we don't need the offset of them                ]                */            {                ulli prime=primes.at(index);//take a prime number                if(ENABLE_OUTPUT)                    cout<<"sieve "<<prime<<" multiples"<<endl;                ulli i;                //starting from the next segment + the offset of the first multiple of the current prime number                for(i=SEGMENT_SIZE*segment + offset.at(index)  ;i<SEGMENT_SIZE*segment+SEGMENT_SIZE;i+=prime)//i=SEGMENT_SIZE*segment + offset.at(index) [may cause overflow]                {                    if(ENABLE_OUTPUT)                        cout<<"remove "<<i<<" in "<<i-SEGMENT_SIZE*segment<<endl;                    p.set(i-SEGMENT_SIZE*segment,0);// (i) is the actual number                    //(i) is not prime                }                //new offset                if(ENABLE_OUTPUT)                        cout<<"change offset for "<<prime<<" from "<<offset.at(index)<<" to "<<i-(SEGMENT_SIZE*segment+SEGMENT_SIZE)<<endl;                offset.at(index)=i-(SEGMENT_SIZE*segment+SEGMENT_SIZE);                //change the offset for the next segment            }            for(ulli i=0;i<SEGMENT_SIZE;i++)//pick up the new primes                if(p.test(i)){//still 1 ! it's prime                    ulli prime=i+SEGMENT_SIZE*segment;//calculate the number                    primes.push_back(prime);//save it as prime                    offset.push_back(prime*prime-(SEGMENT_SIZE*segment+SEGMENT_SIZE));//save it's offset to use in next segments                    //we don't need the offset of the prime>sqrt(MAX_NUMBER_TO_SIEVE)                    if(ENABLE_NEW_PRIMES_OUTPUT|ENABLE_OUTPUT)                        cout<<"new prime "<<prime<<endl;                }        }        //end step2 :p    return 0;}
فيما يلي الكود نفسه ولكن بإزالة أسطر الطباعة والتتبع

#include <bitset>#include <vector>using namespace std;int main(){    typedef unsigned long long int ulli;//use long long to avoid overflow    const ulli MAX_NUMBER_TO_SIEVE  =100;//try 10^9 :)    /*there is only 2 limits on MAX_NUMBER_TO_SIEVE :    1- sqrt(MAX_LONG_LONG)[because of overflow]    2- size of the vector that saving the primes    */    const ulli SEGMENT_SIZE         =5;//the minimum Size is 2,the maximum depend on size of bitset    const ulli NUMBER_OF_SEGMENTS   =MAX_NUMBER_TO_SIEVE/SEGMENT_SIZE;    vector<ulli>primes;//vector to save primes    /*remember that vector is bad when stretching ,make the whole thing slow      you can use linked-list or array of max_number_of_primes < 1000000000    */    vector<ulli>offset;//vector to save how far is the first multiple of the prime from the start of the segment    bitset<SEGMENT_SIZE>p;//only few bits could be used to sieve all primes    //step 1: start with seiving primes < SEGMENT_SIZE    p.set();    p.set(0,0);    p.set(1,0);    for(int i=2;i<SEGMENT_SIZE;i++)        if(p.test(i))            {                primes.push_back(i);                int j;                for(j=i*i;j<SEGMENT_SIZE;j+=i)//j=i*i may cause overflow[not really]                    p.set(j,0);                offset.push_back(j-SEGMENT_SIZE);            }    //End step 1;and segment 0 is ready    //step 2:repeate sieve for all segments    for(ulli segment=1;segment<NUMBER_OF_SEGMENTS;segment++)//every segment is SEGMENT_SIZE number        {            p.set();//all ones , assume that they are primes            for(ulli index=0; index<primes.size();index++)//for all primes inside vector(primes)            {                ulli prime=primes.at(index);//take a prime number                ulli i;                //starting from the next segment + the offset of the first multiple of the current prime number                for(i=SEGMENT_SIZE*segment + offset.at(index)  ;i<SEGMENT_SIZE*segment+SEGMENT_SIZE;i+=prime)//i=SEGMENT_SIZE*segment + offset.at(index)                {                    p.set(i-SEGMENT_SIZE*segment,0);// (i) is the actual number                    //(i) is not prime                }                //new offset                offset.at(index)=i-(SEGMENT_SIZE*segment+SEGMENT_SIZE);                //change the offset for the next segment            }            for(ulli i=0;i<SEGMENT_SIZE;i++)//pick up the new primes                if(p.test(i)){//still 1 ! it's prime                    ulli prime=i+SEGMENT_SIZE*segment;//calculate the number                    primes.push_back(prime);//save it as prime                    offset.push_back(prime*prime-(SEGMENT_SIZE*segment+SEGMENT_SIZE));//save it's offset to use in next segments                    //we don't need the offset of the prime>sqrt(MAX_NUMBER_TO_SIEVE)                }        }    return 0;}
الفكرة الأساسية في SSoE هي مصفوفة الـoffset التي تحتفظ ببعد أول رقم من مضاعفات العدد الأولي الذي نقوم بغربلة مضاعفاته عن أول عنصر في الsegment

وفقك الله

والله ولي التوفيق

1

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه

من فضلك سجل دخول لتتمكن من التعليق

ستتمكن من اضافه تعليقات بعد التسجيل



سجل دخولك الان

  • يستعرض القسم حالياً   0 members

    لا يوجد أعضاء مسجلين يشاهدون هذه الصفحة .