امتحان تقسیم

امتحان تقسیم ^*[۱] الگوریتمی است که محاسبات بالایی رو می طلبد ولی فهمیدن آن بسیار ساده است. سادگی پیاده سازی آن باعث شده که هنوز هم از آن برای دستگاه‌های با حافظه کم استفاده شود. مثل ماشین حساب‌های که نمودار می کشند.

ایده اصلی

امتحان تقسیم با دریافت عدد n، و تقسیم کردن عدد n بر تمام اعداد بزرگ تر از صفر و کوچک تر از n تمام عامل‌های اول n را پیدا می کند

متد

عدد n را میگیرد (در تمام این متن n عددی است که باید تجزیه شود) امتحان تقسیم برای تمام اعداد ممکن امتحان می‌کند که آیا عدد n بر آنها بخش پذیر هست یا خیر. تست این بخش پذیری‌ها از عدد 2 شروع می‌شود وادامه پیدا می‌کند ولی یکی از نکات منفی این روش این است که اگر یک عدد بر 2 بخش پذیر نباشد بخش پذیری آن را بر 4 دوباره تست می‌کند همچنین برای 3 و مضارب 3 و همچنین مضارب بقیه اعداد. از این رو برای کمینه شدن تقسیم‌ها می توان فقط بخش پذیری به اعداد اول را تست کرد. علاوه بر این اعدادی که بخش پذیری بر آن‌ها باید تست شود نباید از $\scriptstyle\sqrt{n}$ بیشتر باشند چون اگر n بر q بخش پذیر باشد آنگاه داریمn = p×q و اگر q کوچک تر از p باشد بخش پذیری بر q یا عامل‌های اول آن زود تر تست می شود.

فرض کنید P(i) i امین عامل است چنان کهP(1) = 2, P(2) = 3, P(3) = 5 آنگاه آخرین عامل اول با ارزش که ممکن است عامل اول n باشد (P(i است که P(i + 1)² > n این تساوی نشان می دهد (P(i + 1 یکی از عامل هاست برای مثال تست کردن 2 و 3 و 5 برای n‌های کوچک تر از 49 کافی است (نه فقط کوچک تر از 25) چون مربع عدد اول بعدی 49 است. این خیلی خوب است ولی معمولاً بکار بستن آن برای یک n محاسبات و کار بیشتری را نسبت به حالتی که (P(i + 1 را هم تست کنیم می طلبد بنابراین $\scriptstyle P(i) \le \sqrt{n}$

یک مثال از الگوریتم امتحان تقسیم که بخش پذیری بر همه اعداد را تست می کند. (به زبان جاوا)

import java.util.Scanner;
class TrialDivision {
    public static void main(String[] argv) {
        Scanner sc = new Scanner(System.in);
        int numToBeFactored = sc.nextInt();
 
        for (int i=2; i < 0.5 + Math.sqrt(numToBeFactored); i++) {
            double tmp=numToBeFactored/(double)i;
            if (tmp == (int)tmp) {
                System.out.println(i + ", " + (int)tmp);
            }
        }
    }
}

امتحان تقسیم تضمین می‌کند که عامل‌های اول n را پیدا می کند. این الگوریتم تمام عامل‌های اول ممکن را امتحان می‌کند بنا بر این اگر هیچ عامل اولی پیدا نشود یعنی n عدد اول است و اگر پیدا شود یعنی n عددی مرکب است.

برای n هایی که حد اقل یک عامل کوچک داشته باشند امتحان تقسیم سریع عمل می کند. توجه به این موضوع لازم است که اگر به صورت تصادفی n انتخاب شود 50% احتمال دارد که 2 یکی از عامل‌های آن باشد و 33% احتمال دارد که 3 یکی از عامل‌های آن باشد و ... این قابل نشان دادن است که 88% اعداد مثبت یک عامل کوچک تر از 100 دارند و 97% یک عامل کوچک تر از 1000 دارند. الگوریتم‌های دیگر موثر تر وکارا تری نیز وجود دارند.

پاورقی

^ Trial division

منبع

division Trial division