الگوریتم غربال اراتستن
الگوریتم غربال اراتستن ( seive of erathosten ) یکی از معروفترین الگوریتم های معروف برای پیدا کردن اعداد اول هست که پیچیدگی زمانی آن ( O( nlglg n می باشد .
در این جا سعی بر این داریم که الگوریتمی را توضیح دهیم که این الگوریتم را با پیچیدگی زمانی خطی بهبود بدهد .
ابتدا الگوریتم غربال ارتستن را توضیح داده سپس سراغ الگوریتم بهبود یافته خواهیم رفت .
الگوریتم غربال اراتستن : از عدد 2 شروع کرده ، تمام ضرایب آن که عددی مرکب خواهد بود را حذف می کنیم ، سپس سراغ اولین عدد حذف نشده ی بعدی می رویم ( که این عدد هم طبیعتا اول هست ) و این کار را ادامه می دهیم .
پیاده سازی این الگوریتم به صورت زیر می باشد
// cpp code #include <iostream> using namespace std; const int maxn=1000*1000; bool v[maxn]={true,true}; #define FOR(i,t,n) for((i)=(t);(i)<(n);(i)++) void sieve(int n){ int i,j; FOR(i,2,n)if(!v[i]) for(j=i+i;j<n;j+=i) v[j]=true; }
کد یه کم بهتر :
// cpp code a bit better #include <iostream> using namespace std; const int maxn=1000*1000; bool v[maxn]={true,true}; void sieve(int n){ int i,j; for(i=2;i*i<n;i++)if(!v[i]) for(j=i*i;j<n;j+=i) v[j]=true; }
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
خوب میریم سراغ الگوریتم با پیچیدگی خطی :
این کار را با استفاده از اصل اکسترمال انجام می دهیم . به ازای هر عدد کوچکترین عامل اول آن را بدست می آوریم . که آن را در آرایه ی lp ذخیره می کنیم . و همین طور باید آرایه ای داشته باشیم که اعداد اول را در آن مشخص کنیم که آن را pr می نامیم .
به ازای هر عدد i بین 2 و n دو حالت داریم :
1 - lp[i]==0 ، که یعنی این که هنوز کوچکترین عامل اول این عدد پیدا نشده است ، پس کوچکترین عامل اول آن خودش خواهد بود
2 - lp[i]!=0 ، که یعنی این که کوچکترین عامل اول این عدد مشخص شده است .
برای هر دو حالت ، تمام اعداد اول کوچکتر از این عدد را در نظر میگیریم ، و تا زمانی که از کوچکترین عامل اول این عدد ، کوچکتر هست ، ضرایب آن را حذف می کنیم .
پیاده سازی الگوریتم :
// cpp code #include <iostream> using namespace std; const int maxn=1000*1000; int lp[maxn],pr[maxn]; int size; // size of prime numbers void sieve_new(int n){ int i,j; for (i=2; i<n; ++i) { if (lp[i] == 0) { lp[i] = i; pr[size++]=i; } for (j=0; j<size && pr[j]<=lp[i] && i*pr[j]<n; ++j) lp[i * pr[j]] = pr[j]; } }
اثبات صحیح بودن الگوریتم و اثبات خطی بودن الگوریتم :
نکته ی ساده و جالبی که وجود دارد این است که هر عدد را می توان به صورت i= lp[i]*x نوشت که عملا این عدد حتما چک شده است و نکته ی جالبتری که وجود دارد این است که هر i فقط یک بار چک می شود علت آن هم این است که می دانیم فرض کنید برای یک عدد خاص مانند n ، دو عدد مانند i و j وجود دارند که n برابر i*p و j*q شده است که در این صورت یعنی کوچکترین عامل n هم p هست و هم q که در این صورت یعنی p=q و مشخصا i =j خواهد بود .
توانستیم الگوریتمی خطی ارایه بدهیم ، ولی عملا خود الگوریتم غربال ، با الگوریتم خطی خیلی فرقی نمی کند :)
ولی خوب نکته ای که هست این است که حداقل یه تغییر مثبت داشته ایم و از همه مهم تر این ایده ی کوچکترین مقسوم علیه می باشد که بسیار ایده ی پر کاربردی هست .
( برای این که جالب بودن این ایده را ببینید می تونید این سوال را با پیچیدگی زمانی خطی حل کنید )
با تشکر
عید نوروز 1391 ( باورم نمیشه :) . تو عید حوصله ام شد اینو بنویسم ، له لهم ، داغونماااا.... )