تست اول بودن عدد

از shaazzz
پرش به ناوبری پرش به جستجو

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

bool isPrime(int x) 
{
    for (int d = 2; d * d <= x; d++)
    {
        if (x % d == 0)
            return false;
    }
    return true;
}

این یک راه ساده برای چک کردن اول بودن است و می توان آن را کمی بهینه تر کرد . مثلا فقط می توان اعداد فرد را چک کرد چون تنها عددد اول زوج ۲ است . می توانید بهینه سازی های دیگری را هم در تجزیه اعداد بخوانید.

بررسی اول بودن یک عدد با استفاده از قضیه فرما[ویرایش]

توجه داشته باشید که این راه یک راه احتمالی است طبق قضیه فرمای کوچک به ازای عدد اول و عدد که نسبت به هم اول هستند داریم : و اغلب برای اعداد مرکب درست نیست و ما با استفاده از این می توانیم اول بودن را چک کنیم . برای همین یک عدد مانند از بازه انتخاب می کنیم و چک میکنیم که معادله بالا درست است یا نه . اگر درست نبود یعنی متوجه می شویم که نمی تواند اول باشد. ولی ممکن است که این معادله برای یک عدد مرکب هم درست باشد . بنابراین اگر معادله برقرار بود نمی توانیم بگوییم که عدد اول است یا نه ولی احتمال می دهیم که باشد . توجه کنید که اگر تمام اعداد ممکن را در بازه بالا چک کنیم می تونیم ثابت کنیم که عدد اول هست یا نه ولی اینکه بخواهیم تمام های ممکن رو چک کنیم برای های بزرگ کار خوبی نیست و روش اول منطقی تر و بهتر است . بنابراین تعداد رندوم انتخاب می کنیم . اگر معادله به ازای تمام های رندوم درست بود به احتمال خوبی عدد اول است.

bool probablyPrimeFermat(int n, int iter=5) 
{
    if (n < 4)
        return n == 2 || n == 3;

    for (int i = 0; i < iter; i++) 
    {
        int a = 2 + rand() % (n - 3);
        if (binpower(a, n - 1, n) != 1)
            return false;
    }
    return true;
}

برای اینکه سریعتر را محاسبه کنیم می توانیم از الگوریتم توان رسایی دودوییاستفاده کنیم که در اجرا می شود. اما با وجود چک کردن چند هم مشکلی وجود دارد:)) اعداد مرکبی هستند که به ازای تمام هایی که نسبت به اول هستند برفرار است . برای مثال عدد به چنین عددی کارمایکل می گویند و این روش درصورتی می تواند این عدد را تشخیص دهد که مرکب است که ایی انتخاب شود که باشد . با این وجود این روش همچنان استفاده می شود چون سریع است و اعداد کارمایکل بسیار نادر هستند به طوری که تنها عدد کارمایکل تا داریم .

مسائل تمرینی[ویرایش]