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
