خیلی‌ها کامل نیستند!

مساله: برنامه‌ای بنویسید که بگوید یک عدد کامل است یا خیر.

اما عدد کامل چیست؟ به ریاضی بازمی‌گردیم، عدد کامل عددی است که مجموع مقسوم علیه‌های سره آن برابر خود عدد باشد.

(مجموع مقسوم علیه‌های سره یعنی جمع مقسوم علیه‌های یک عدد به جز خود عدد مثلا برای عدد 15 داریم 8=5+3+1 مقسوم علیه‌های عدد 15 برابر 1 و 3 و5 و 15 هستند)‌

حال چگونه مقسوم علیه‌های یک عدد را به دست بیاوریم؟ می‌دانیم که مقسوم علیه عددی است که وقتی عدد را بر آن تقسیم کنیم خارج قسمت برابر صفر می‌شود و این را هم می‌دانیم که بزرگ‌ترین مقسوم علیه یک عدد خود عدد است.

حال باید یک برنامه بنویسیم که مقسوم علیه‌های یک عدد را پیدا کند، راه ساده این است که در یک حلقه که از 1 شروع می‌شود و تا خود عدد ادامه پیدا می‌کند، خود عدد را بر اندیس حلقه تقسیم کنیم و اگر خارج قسمت برابر صفر شد یعنی اندیس حلقه برابر مقسوم علیه یک عدد است. کد آن به صورت زیر است:

for (int i = 1; i «= number; i++) {

if(number%i == 0)

print i; }

Print i تمام مقسوم علیه‌های یک عدد را چاپ می‌کند. حالا بیاییم قطعه کد بالا را تبدیل به قطعه کدی برای حل مساله خودمان بکنیم.

صورت مساله مجموع تمام مقسوم علیه‌های سره یک عدد را می‌خواهد پس ما باید مقدار i را با یک متغیر دیگری مثلا به اسم sum جمع کنیم، یعنی:

for (int i = 1; i «= number; i++) {

if(number%i == 0)

sum+=i; }

اما آیا این جواب ماست؟ خیر، چون خود عدد را نیز جمع می‌کند پس شرط پایان‌پذیری حلقه را به صورتI«number تغییر می‌دهیم، یعنی برای تمام i‌های کوچک‌تر از خود عدد. در نهایت مقدار sum را با خود عدد مقایسه می‌کنیم اگر برابر بودند یعنی عدد کامل است و خروجی مناسب را چاپ می‌کنیم.

حال بیایید کد بالا را قدری بهتر کنیم.

می دانیم هر عدد بر 1 تقسیم پذیر است پس مقدار sum را برابر 1 قرار می‌دهیم و حلقه را از 2 شروع می‌کنیم، این طوری حلقه ما یک مرحله کمتر اجرا می‌شود.

از ریاضی به یاد داریم که مقسوم‌علیه‌ها حالت قرینه دارند یعنی مقسوم علیه‌های یک عدد تا نصف آن عدد را در نظر بگیرید، مقسوم علیه‌های بزرگ‌تر از نصف عدد حاصل تقسیم عدد بر مقسوم علیه‌های نصفه اول است. پس ما نیازی نداریم که همیشه یک حلقه را تا خود عدد ادامه دهیم کافیست که تا نصف عدد برویم و سپس مقسوم علیه‌های عدد را در یک ارائه ذخیره کنیم سپس در بیرون حلقه عدد را بر تک‌تک آنها تقسیم کنیم تا باقی مقسوم علیه‌ها پیدا شوند. چرا این کار را می‌کنیم؟ بخاطر این‌که تعداد تکرار‌های حلقه خود را کم کنیم، هیچ عددی وجود ندارد که تعداد مقسوم علیه‌های کوچک‌تر از نصف خودش برابر نصف عدد باشد، طبق حل اول مساله گفتیم که تعداد تکرار حلقه برابر خود عدد 1- است، حالا ما این مقدار را به نصف کاهش دادیم و سپس برای نصفه باقی یک حلقه دیگر نوشتیم پس همیشه تکرار حلقه‌های ما کمتر از خود عدد1- است. کد آن را به صورت زیر می‌نویسیم:

int number = 6;

int sum = 1;

List«int» data-x-items = new List«int»();

for (int i = 2; i « number / 2; i++) {

if (number % i == 0) {

sum += i;

items.Add(i); }}

مقادیری که در itemsقرار می‌گیرند عبارتند از تمامی مقسوم علیه‌هایی که از نصف عدد کوچک‌تر هستند. پس خارج از حلقه باید مقسوم علیه‌های بزرگ‌تر از نصف را با مقدار sum جمع کنیم که این کار را به صورت زیر انجام می‌دهیم:

for (int i = 0; i « items.Count; i++) {

int x = number / items[i];

sum += x;}

این قطعه کد برای اعدادی که بزرگ هستند به مراتب بهتر از قطعه کد‌های بالایی است. اما آیا این کد بهینه است؟

جواب، خیر است، پس کد را عوض می‌کنیم. می‌دانیم که اگر عددی اول باشد مجموع مقسوم علیه‌های سره آن برابر 1 است!

پس قبل از اجرا شدن 2 حلقه بالا کافی است که بررسی کنید یک عدد اول هست یا خیر اگر اول بود دیگر کامل نیست.

این کار یک مزیت دارد آن هم این است که اگر عدد اول بزرگی را خواستید بررسی کنید، دیگر همه مراحل را تکرار نمی‌کنید و همانجا صراحتا «جواب کامل نیست» را در خروجی چاپ می‌کنید، عیب این روش در این است که اگر عدد بزرگ بوده و اول هم نباشد ما زمانی را صرف چک‌کردن اول بودن عدد کرده‌ایم، اما در مقاله‌های پیش ثابت کردیم که چک‌کردن اول‌بودن یک عدد را می‌توان در هزارم ثانیه انجام داد پس می‌توان از مدت زمان اجرای این عملیات صرف نظر کرد.

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