این اول هست، اون نیست!

}(public static bool isPrime(int args

for (int i = 2; i « args; i++){

if (args % i == 0) return false;}

return true;

{

خب این سه خط جواب می‌دهد و درست است، اما تنها برای اعداد کوچک. فرض کنید عدد ورودی 2147483647 باشد، برای چک کردن اول بودن این عدد زمانی معادل با 11ثانیه باید صرف شود که این زمان زیادی است. یک مقدار الگوریتم را بهتر می‌کنیم تا این زمان کاهش پیدا کند، بگذارید یک مقداری اعداد اول را در ریاضی بررسی کنیم. عدد 2 تنها عدد اول زوج است، پس اگر عدد ورودی 2 بود، اول است و دیگر هیچ عدد اول زوجی وجود ندارد. پس ما اعداد زوج را هم حساب نمی‌کنیم و اگر عدد ورودی بر 2 بخش‌پذیر بود نیز تابع با نتیجه false به‌کار خودش خاتمه می‌دهد. خب، با این کار ما نصف اعداد 2 تا عدد ورودی x را بررسی نمی‌کنیم و فقط اعداد فرد را بررسی می‌کنیم، که کد آن به‌صورت زیر است:

public static bool isPrime(int args){

if (args == 2) return true;

else if (args % 2 == 0) return false;

for (int i = 3; i « args; i = i + 2 ){

if (args % i == 0) return false;}

return true;

}

بسیار خوب، بار دیگر این کد را با عددی که در بالا ذکر شد تست می‌کنیم. نتیجه این است که کد جدید 5ثانیه طول می‌کشد یعنی از نصف هم کمتر. پس ما به الگوریتم به ‌نسبت بهتری رسیدیم. ولی بگذارید یک مقداری بیشتر کد را بررسی کنیم و این زمان را کمتر کنیم.

برای اینکه الگوریتم را کمی بهتر کنیم‌، فرض کنید A*B=C است. برای اینکه A+B بیشترین مقدار را داشته ‌باشند، باید A=B باشد (به این خاطر بررسی می‌کنیم که مجموع دو عدد A و B بیشترین مقدار را داشته ‌باشد که بازه‌ لازم برای تشخیص عدد اول بزرگتر شود تا نتیجه با دقت بیشتری به‌دست آید)، یعنی A به توان2 برابر C باشد در نتیجه (A=B=Sqrt(C است.

در نتیجه اگر C عددی اول نباشد قطعا یک ریشه کوچکتر مساوی عدد(Sqrt(C خواهد داشت (اگر C یک ریشه بزرگتر از جذر خودش داشته ‌باشد ریشه دیگر قطعا کوچکتر از جذر C خواهد بود). در نتیجه اگر بین عدد 3 و جذر عدد ورودی یک عدد غیراول وجود داشته ‌باشد، در نتیجه عدد ورودی اول نیست، در غیر این‌صورت عدد ورودی اول است.

الگوریتم ما با این روش خیلی بهتر از قبل شد. اگر در روش قبل نصف اعداد بررسی می‌شدند، در این روش اعداد فرد بین 3 و جذر یک عدد مورد بررسی قرار می‌گیرند و از آنجا که درجه رشد مجذور کمتر از نصف عدد است، مثلا اگر عدد ورودی برابر 9 باشد نصف آن برابر 5/4 و جذر آن برابر 3 است و در عددی مثل 64 اختلاف بین جذر و نصف عدد برابر 22 است و در اعداد بزرگتر این اختلاف بیشتر می‌شود، بنابراین جستجو بین اعداد فرد بین 3 و جذر یک عدد و اعداد فرد موجود بین آنها هزینه کمتر و بازدهی بیشتری دارد.

حال الگوریتم را طبق توضیحات گفته شده بازنویسی می‌کنیم:

public static bool isPrime(int args){

double sqrtN = Math.Sqrt(args);

if (args == 2) return true;

else if (args % 2 == 0) return false;

for (int i = 3; i «= sqrtN; i = i + 2){

if (args % i == 0) return false;}

return true;

}

این الگوریتم برای عدد 2147483647 چیزی در حدود ?هزارم میلی‌ثانیه طول می‌کشد، یعنی حتی به یک میلی‌ثانیه هم نمی‌رسد. خب الان به یک الگوریتم بهینه برای پیدا کردن عدد اول رسیدیم. حال بخش دوم مساله، پیدا کردن تعداد اعداد اول موجود در یک بازه است. برای این مساله نیاز به الگوریتم جستجوی مناسب داریم که داده‌ها را با استفاده از تابع isPrime فیلتر کنیم و به‌صورت بهینه، تمامی اعداد اول موجود در یک بازه را به‌دست بیاوریم.

امیر بهاءالدین سبط الشیخ