همه چیز درباره اعداد اول ، الگوریتم غربال
وبرنامه نویسی اعداد اول را در اینجا پیدا میکنید
تا بحال کلمه الگوریتم غربال یا غربال اراتستن رو شنیدین؟یا بهتره اینطوری بپرسم:میدونید اعداد اول به چه روشی از بین مجموعه اعداد طبیعی مشخص میشوند؟و سئوال آخر اینکه اگر شما بخواهید به کمک برنامه نویسی کامپیوتری اعداد اول را پیدا کنید چه کار میکنید؟برای دیدن پاسخ سئوالهای بالا چند دقیقه ای وقتتون رو با رهیار بگذرونید.براتون جالب خواهد بود.
اعداد اول یکی از شگرفترین مفاهیم ریاضی هستند که همواره قدرت ریاضیدانان و برنامه نویسان را به چالش کشیده است. سختی تولید این اعداد باعث شده است همواره افراد سعی در فرموله کردن آن ها داشته به دنبال الگوریتم های قدرمندتری برای تولید آن ها باشند.
برای تشکیل فهرست همه عددهای اول تا یک عدد صحیح مفروض n میتوان همه عددهای صحیح کوچکتر از n را به ترتیب نوشت، نخست همه آنهایی را که مضرب 2 هستند خط زده سپس همه آنهایی را در میان اعداد باقیمانده که مضرب 3 هستند خط زده و همینطور به حذف سپس همه آنهایی را در میان اعداد باقیمانده که مضرب 3 هستند خط زد، و همینطور به حذف اعداد مرکب ادامه داد تا هیچ عدد مرکبی باقی نماند.
این فرایند که به «غربال اراتستن» معروف است، تمام عددهای اول تا n را مشخص میسازد. جدولهای کاملی از عددهای اول تا حدود 10000000 به تدریج به وسیله صورتهای ظریفتری از این روش تهیه شدهاند، و این جدولها توده عظیمی از دادههای تجربی درباره توزیع و ویژگیهای اعداد اول در اختیار ما میگذارند.
براساس آنها میتوانیم حدسهای بسیار موجهی بزنیم (چنانکه گویی نظریه اعداد یک علم تجربی است) که اثبات آنها اغلب بسیار دشوار است.
یکی از قدیمیترین و کاراترین الگوریتم تولید اعداد اول، الگوریتم غربال است که هم اکنون انواع بهبود یافته آن به عنوان سریعترین روش تولید اعداد اول استفاده می شوند. ما برای درک بهتر این الگوریتم از ساده ترین آن شروع می کنیم و به مرور زمان ضمن تلاش خودمان برای بهبود آن، از انواع بهبود یافته که در برنامه های مختلف کابرد دارند استفاده خواهیم کرد.
پس در ادامه مطلب همراه ما باشید تا طریقه برنامه نویسی تولید اعداد اول را یاد بگیرید
پس در ادامه مطلب همراه ما باشید تا طریقه برنامه نویسی تولید اعداد اول را یاد بگیرید
-- الگوریتم --
روش غربال همانطور که از نام آن بر می آید با حذف اعداد مرکب ، اعداد باقی مانده را به عنوان اعداد اول معرفی می کند. با عدد 2 شروع می کنیم و تمام مضارب آن را علامت می زنیم، سپس با عدد 3 همین کار را انجام می دهیم و تا جذر عدد N ) N همان عددیست که می خواهیم اعداد اول تا آن را پیدا کنیم ) پیش می رویم ( چرا تا جذر N ؟ ) . و این نکته را ( به عنوان یک بهبود زمان از نوع حذف عملیات ) مد نظر داریم که تنها مضارب اعدادی را حذف می کنیم که خود عدد، عدد اول باشد. چرا که اگر عدد اول نباشد ما عملیات بیهوده ای انجام داده ایم و مضارب یک عدد مرکب توسط عامل های آول آن عدد علامت زده می شوند. در این روش چون فقط به یک علامت نیاز داریم پس کمترین حجم ممکن را برای این Flag در نظر می گیریم ، در این جا 1 بایت ( 1 بایت خود شامل 8 بیت است که می توانیم با تعدادی عمل اضافی به جای 1 بایت از یک هشتم آن یعنی یک بیت استفاده کنیم. این مورد را در ارسال های بعدی بررسی می
کنیم.) فضا از نوع Char را لحاظ می کنیم. پس تا اینجا به ازای عدد N، نیاز به N بایت فضا داریم. ( اعداد زوج به سادگی قابل حذف هستند که باعث نصف شدن فضای مورد نیاز می شوند. این مورد هم در ارسال ها بعدی بررسی می شود.). چون Flag ما در اینجا عدد 1 است پس هر خانه ای از آرایه که مقدار اولیه خود ( در این جا 0 ) را داشته باشد، یعنی علامت نخورده است پس عدد اول است. متغیر div هم تعیین می کند عملیات حذف مضارب یک عدد اول تا کجا پیش رود. اگر به داخلی ترین دستور درون if داخلی نگاه کنید، میبینید که عملیات مورد استفاه جمع است. چرا جمع؟
مگر قرار نبود مضارب حذف شوند؟ مگر مضارب با ضرب تولید نمی شوند؟ بله درست است. مضارب با ضرب تولید می شوند ولی زمانی که یک عدد ثابت ( در این جا i ) قرار است در اعداد 2 ، 3 ، 4 ، 5، و .. ضرب شود ( اختلاف اعداد یک واحد است ) پس در هر مرحله مقداری معادل عدد ثابت باید افزوده شود ( s+=i ) که اینکار با جمع هم قابل اجراست.
وقتی می توانیم یک عملیات را با جمع انجام دهیم ، چرا به سراغ ضرب برویم. تصور کنید می خواهید i را در 1569 ضرب کنید. در این برنامه ما در مرحله قبلی حاصل ضرب i در 1568 را بدست آورده ایم. خوب وقتی می توانیم با یک بار افزودن i به جواب قبلی، جواب این مرحله را داشته باشیم، چه لزومی دارد i را 1569 ضرب کنیم. حالا این کاهش عملیات را برای تمام اعداد اول تا N محاسبه کنید که خواهید دید چقدر این حقه ساده در کاهش زمان برنامه موثر است. به همین سادگی. حلقه اصلی دوم هم تعداد اعداد اول تا N را می شمارد و در صورتی که دستور printf موجود در آن را از حالت comment خارج کنید، تمام اعداد اول تا N را نیز چاپ می کند ( البته به غیر از اولین عدد اول یعنی 2 ).
-- کد برنامه --
کد:
/*
Name: Prime Sieve Method
Description: Calcualres all the primes less than n
*/
#include<stdio.h>
#include<math.h>
#include<time.h>
#include<conio.h>
#define MAX 1000000000
long prime(long);
char p[MAX]={0};
main()
{
long n,primeCounter; _beginthread();
scanf("%ld",&n);
double t1 = clock();
primeCounter = prime(n);
printf("\n\n %ld Primes detected in %.3lf seconds",primeCounter,(double)(clock()-t1)/CLOCKS_PER_SEC);
#include<math.h>
#include<time.h>
#include<conio.h>
#define MAX 1000000000
long prime(long);
char p[MAX]={0};
main()
{
long n,primeCounter; _beginthread();
scanf("%ld",&n);
double t1 = clock();
primeCounter = prime(n);
printf("\n\n %ld Primes detected in %.3lf seconds",primeCounter,(double)(clock()-t1)/CLOCKS_PER_SEC);
getch();
return 0;
}
long int prime(long int x)
{
long i,j,max=sqrtl(x),div,s,primeCounter=1;
for(i=2;i<=max;i++)
{
if(!p[i])
{
div=x/i;
for(j=i,s=(i*i)-i;j<=div;j++)
{
if(!p[s+=i])
p[s]=1;
}
}
}
for(i=3;i<=x;i+=2)
{
if(!p[i])
{
primeCounter++;
// printf("%ld : %ld\n",primeCounter,i);
}
}
return primeCounter;
}
-----------------------------------------
نمونه الگوریتم غربال اراتستن در زبان ++c :
return 0;
}
long int prime(long int x)
{
long i,j,max=sqrtl(x),div,s,primeCounter=1;
for(i=2;i<=max;i++)
{
if(!p[i])
{
div=x/i;
for(j=i,s=(i*i)-i;j<=div;j++)
{
if(!p[s+=i])
p[s]=1;
}
}
}
for(i=3;i<=x;i+=2)
{
if(!p[i])
{
primeCounter++;
// printf("%ld : %ld\n",primeCounter,i);
}
}
return primeCounter;
}
-----------------------------------------
نمونه الگوریتم غربال اراتستن در زبان ++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";
}
------------------------------------------------
نمونه دیگری از الگوریتم غربال اراتستن در زبان c :
نمونه دیگری از الگوریتم غربال اراتستن در زبان 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);*/
}
}
طبقه بندی: ریاضیات،