منو
 کاربر Online
643 کاربر online

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

چاپ
علوم ریاضی > ریاضی > شاخه های ریاضی > ریاضی محض



Untitled Document






برای تشکیل فهرست همه عددهای اول تا یک عدد صحیح مفروض n می‌توان همه عددهای صحیح کوچکتر از n را به ترتیب نوشت، نخست همه آنهایی را که مضرب 2 هستند خط زده سپس همه آنهایی را در میان اعداد باقی‌مانده که مضرب 3 هستند خط‌‌ زده و همین‌طور به حذف سپس همه آنهایی را در میان اعداد باقی‌مانده که مضرب 3 هستند خط زد، و همین‌طور به حذف اعداد مرکب ادامه داد تا هیچ عدد مرکبی باقی نماند. این فرایند که به «غربال اراتستن» معروف است، تمام عددهای اول تا n را مشخص می‌سازد. جدولهای کاملی از عددهای اول تا حدود 10000000 به تدریج به وسیله صورتهای ظریفتری از این روش تهیه شده‌اند، و این جدولها توده عظیمی از داده‌های تجربی درباره توزیع و ویژگیهای اعداد اول در اختیار ما می‌گذارند. براساس آنها می‌توانیم حدس‌های بسیار موجهی بزنیم (چنانکه گویی نظریه اعداد یک علم تجربی است) که اثبات آنها اغلب بسیار دشوار است.

 


 


 


 


 


 



الگوریتم غربال اراتستن در زبان c :



/* Prime Number Sieve in C: main->p1->p2->p3->p4->...->p99

*/

#include


FILE *user; FILE *fopen();


/* main program to generate successive integers greater than 1*/

main()

{ int integer=2;


user=fopen("/dev/tty","w");

/* /dev/tty is the users terminal.*/


fprintf(user, "Use CTRL/C to stop me....\n");


while (1) p(1,integer++);

/*WAS printf("%d\n", integer++);*/

}


/* C co-function to record a prime and sieve out its multiples from the input*/

/* i is the input and n an index distinguish successive p's*/

/* Each process initializes itself when i=0. */

p(n,i) int n,i; /*WAS main() */

{

static int prime100, integer100;


/* restart */ static int QS100;

/*debug fprintf(stderr,"p(%d,%d)QS=%d,prime=%d,int=%d,\n",n,i,QSn,primen,integern);*/


/*assuming static data initially =0*/

switch(QSn)

{case 0:goto Q0;case 1:goto Q1; }

Q0:


if(n==99)return;/*'p99' is the end of the chain/pipeline.*/


primen=i; /*WAS scanf("%d", &prime);*/


fprintf(user,"%d is prime number %d\n",primen,n);


while(1){

/* suspend; */

QSn=1; return; Q1: integern=i;

/*WAS scanf("%d", &integer);*/


if (integern % primen )

p(n+1, integern);/*WAS printf("%d\n",integer);*/

}


}



الگوریتم غربال اراتستن در زبان ++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://en.wikipedia.org/wiki/Eratosthenes%27_Sieve
http://tunes.org/HLL/examples/sieve.html




تعداد بازدید ها: 39680


ارسال توضیح جدید
الزامی
big grin confused جالب cry eek evil فریاد اخم خبر lol عصبانی mr green خنثی سوال razz redface rolleyes غمگین smile surprised twisted چشمک arrow



از پیوند [http://www.foo.com] یا [http://www.foo.com|شرح] برای پیوندها.
برچسب های HTML در داخل توضیحات مجاز نیستند و تمام نوشته ها ی بین علامت های > و < حذف خواهند شد..