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

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

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

الكود التالي مشروح سطراً بسطر , وفيه 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

وفقك الله

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