This wiki has been closed because there have been no edits or logs made within the last 60 days. This wiki is now eligible for being adopted. To adopt this wiki please go to Requests for adoption and make a request. If this wiki is not adopted within 6 months it may be deleted. Note: If you are a bureaucrat on this wiki you can go to Special:ManageWiki and uncheck the "closed" box to reopen it.

تجزیه اعداد

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

تقسیم کردن

این راه راحت ترین الگوریتم برای پیدا کردن عوامل اول است . می توان این الگوریتم رو به این صورت توضیح داد که ما عدد رو بر هر مقسوم علیه ممکنی مانند تقسیم می کنیم و توجه داشته باشید که این غیر ممکن است که عوامل اول یک عدد مرکب مانند بزرگ تر از باشند . بنابراین ما فقط نیاز داریم مقسوم علیه هایی مانند را چک کنیم که باشند و این تمام اول را در به ما می دهد. کوچکترین مقسوم علیه باید اول باشد . سپس عدد را تا جایی که بر این عامل بخش پذیر باشد ، تقسیم می کنیم . (این یعنی توان عامل اول بزرگتر از ۱ است)اگر هیچ عددی در بازه بر بخش پذیر نبود یعنی خود عدد عددی اول است.

vector<long long> trial_division1(long long n) 
{
    vector<long long> factorization;
    for (long long d = 2; d * d <= n; d++) 
    {
        while (n % d == 0) 
        {
            factorization.push_back(d);
            n /= d;
        }
    }
    if (n > 1)
        factorization.push_back(n);
    return factorization;
}

می توانیم بک بهینه سازی برای این الگوریتم ارائه بدهیم به این صورت که ابتدا چک کنیم که عدد زوج هست یا نه و توان عامل ۲ آن چند است. از آنجایی که می دانیم تنها عدد اول زوج ۲ است پس بعد از اینکه توان عامل ۲ در عدد را پیدا کردیم دیگر لازم نیست که اعداد زوج بین را چک کنیم . بنابراین تعداد اعدادی که باید چک کنیم ، تقریبا نصف می شود.

vector<long long> trial_division2(long long n) 
{
    vector<long long> factorization;
    while (n % 2 == 0)
    {
        factorization.push_back(2);
        n /= 2;
    }
    for (long long d = 3; d * d <= n; d += 2) 
    {
        while (n % d == 0) 
        {
            factorization.push_back(d);
            n /= d;
        }
    }
    if (n > 1)
        factorization.push_back(n);
    return factorization;
}

ما می توانیم این روش را گسترش دهیم به این صورت که اگر عدد بر ۳ بخش پذیر نبود ، آنگاه می توانیم از چک کردن مضارب ۳ هم صرفه نظر کنیم . بنابراین فقط نیاز داریم تا اعداد ۵ ، ۷ ، ۱۱ ، ۱۳ ، ۱۷ ، ۲۳ ... را چک کنیم . اگر به الگویی که این اعداد دارند ، نگاه کنیم متوجه می شویم که باقی مانده این اعداد بر ۶ یا ۱ است یا ۵ . پس اگر ما فقط این اعداد رو چک کنیم آنکاه تعدادشان تقریبا ۳۳٪ مقدار قبل می شود . حتی باز هم می توانیم جلوتر پیش برویم تا اعداد کمتری چک کنیم . این کد در ابتدا بخش پذیری عدد بر ۲ و ۳ و ۵ را چک کرده و بعد اعداد اول بین را چک میکند .

vector<long long> trial_division2(long long n) 
{
    vector<long long> factorization;
    while (n % 2 == 0)
    {
        factorization.push_back(2);
        n /= 2;
    }
    for (long long d = 3; d * d <= n; d += 2) 
    {
        while (n % d == 0) 
        {
            factorization.push_back(d);
            n /= d;
        }
    }
    if (n > 1)
        factorization.push_back(n);
    return factorization;
}

چک کردن تنها با استفاده از اعداد اول

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

vector<long long> primes;

vector<long long> trial_division4(long long n) 
{
    vector<long long> factorization;
    for (long long d : primes) 
    {
        if (d * d > n)
            break;
        while (n % d == 0) 
        {
            factorization.push_back(d);
            n /= d;
        }
    }
    if (n > 1)
        factorization.push_back(n);
    return factorization;
}

تجزیه با استفاده از فرما

در ابتدا دقت داشته باشید که عدد فرد مرکب را می توان به صورت اختلاف ۲ عدد مربع کامل نوشت :




int fermat(int n)
{
    int a = ceil(sqrt(n));
    int b2 = a*a - n;
    int b = round(sqrt(b2));
    while (b * b != b2) 
    {
        a = a + 1;
        b2 = a*a - n;
        b = round(sqrt(b2));
    }
    return a - b;
}

مسائل تمرینی