غربال اراتستن

کد:

---

#include <iostream>

using namespace std;

#define MAX 100000000LL

char a[MAX/8+1], p2[8], f, fp2[8];

void init(bool b)
{
    f = 255;
    if (b)
        memset(a, f, sizeof a);
    else
        memset(a, 0, sizeof a);
    p2[0] = 1;
    for (int i = 1; i < 8; i++) p2[i] = p2[i-1]*2;
    for (int i = 0; i < 8; i++) fp2[i] = f-p2[i];
}

void on(int n)
{
    a[n>>3] |= p2[n%8];
}

void off(int n)
{
    a[n>>3] &= fp2[n%8];
}

bool value(int n)
{
    return a[n>>3]&p2[n%8];
}

int main()
{
    init(1);
    int i, j, k;
    off(0);
    off(1);
    for (i = 4; i <= MAX; i += 2) off(i);
    for (i = 3; i <= MAX; i += 2)
        if (value(i))
            for (j = i+i; j <= MAX; j += i)
                off(j);
}

---

این برنامه رو نوشتم ولی 32 ثانیه طول کشید تا جواب بده
لطفا برای سریع تر کردن این غربال راهی پیشنهاد کنید :11:
دستور on برای true کردن خانه مورد نظر است
و off برای false کردن

این کدی که گذاشتین یه حلقۀ تو در تو ای با عمق 3 داره که باعث میشه کند جواب بده.
باید با روشی )dynamic programming یا روش دیگر) این مشکلو بر طرف کنی.

این کد رو پیدا کردم. به زبان c++ امتحانش کن ببین اینم زیاد طول می کشه یا نه؟

کد:

---




// Prime Number Sieve in C++

// Each prime is an object of class Prime

// Notice that the class is developed in terms of what a Prime is held to

// be responsible for in the program.



#include



class Prime{

int p; //A Prime must remember its value

Prime *next; //A Prime must remember where the next prime is.

public:

// A Prime is responsible for making sure it is set up correctly

Prime() { cerr<<"New Prime not initialized\n"; exit(1); }

Prime(const int n) { p=n ; next=(Prime*)NULL; }



// A Prime is responsible for handling possible primes it is sent

void sent(const int n){

if(n%p)

if(next) next->sent(n);

else next=new Prime(n);

}



// A Prime is responsible for printing itself and its next prime (if any)

friend ostream& operator<<(ostream& s, const Prime n)

{ s<<(n.p);

if(n.next){ s<<" "<<(*(n.next));

}

return s;

}



}; // end class Prime



main()

{

Prime *first=new Prime(2);



for( int n=3; n<=100; n++,n++)

first->sent(n);



cout<<*first<<"\n";

}

---

از سایت رشد:

کد:

---

http://daneshnameh.roshd.ir/mavara/mavara-index.php?page=%d8%ba%d8%b1%d8%a8%d8%a7%d9%84+%d8%a7%d8%b1%d8%a7%d8%aa%d8%b3%d8%aa%d9%86&SSOReturnPage=Check&Rand=0

---

ببين، برنامت Error داره،غربال اراتستن همان بودكه اعداد اول را حساب مي كرد؟يادم رفته اگه درسته يك ok بده