آزمون تقسیم

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

ایده اصلی

آزمون تقسیم با دریافت عدد 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)\leq {\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