Sieve of Eratosthene

Eratosthenes เป็นนักคณิตศาสตร์ชาวกรีก ที่คิดค้นสิ่งต่าง ๆ ไว้มากพอสมควร แต่ วันนี้เราจะมาพูดกันถึง การหาค่า prime หรือจำนวนเฉพาะ ที่ใช้วิธีตัดออกทีละชุด (screen หรือ sieve นั่นเอง)
วิธีการของเค้าก็ง่าย ๆ ครับ คือ ในตัวเลขจำกัดจำนวนนึงเราสามารถหาค่า จำนวนเฉพาะได้โดยใช้ ตัวเลขเริ่มต้น (2) เพื่อที่จะนำไป หาค่าที่เป็นตัวคูณเพื่อ screen ตัวที่เป็น ค่าที่เกิดจากการคูณออกจากความน่าจะเป็นที่จะเป็น จำนวนเฉพาะ โดยตัวที่จะนำมาสกรีน ก็นำมาจถึงแค่ ตัวเลขที่ น้อยกว่าหรือเท่ากับ sqrt ของ ค่าสูงสุดที่ต้องการหา (ตรงนี้พิสูจน์ไม่ยาก)
เช่น หาจำนวนเฉพาะ จนถึง 20
2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
ใช้ 2 screen (2^2 = 4 < 20)
2, 3, 5, 7, 9, 11, 13, 15, 17, 19
ใช้ 3 screen (3^2 = 9 < 20)
2, 3, 5, 7, 11, 13, 17, 19
5 ไม่ต้องนำมาสกรีนอีก เพราะ 5^2 > 20
เพราะฉะนั้นค่าที่ไม่ถูกตัดทิ้งทั้งหมดก็คือ เลขจำนวนเฉพาะ
เขียนด้วย C++ ได้ดังนี้

vector<bool> GetPrimeBitSets(int from, int to) 
{
    vector<bool> bs (to + 1); //Create a bool vector to hold a primality
    for(int i = 0; i < to + 1; i++) //Initialize the primality vector
    {
        bs[i] = bool(i & 1);        //even number will be set as false
    }
    int j = 0;
    from = (from <= 3)? 3 : from; 
    bs[0] = false;
    bs[1] = false;
    bs[2] = true;                   //2 is prime
    bs[3] = true;                   //3 is prime
    for(int i = 3; i * i <= to; i += 2) //All odds numbers are considering
    {
        if(!bs[i]) continue;        //if the number is not a prime then no need to do
        for(j = i + i; j <= to; j += i) // populate all the multiply of i
        {       
            bs[j] = false;
        }       
    }
    return bs;                      //when done, the left number are prime
}