This wiki has no edits or logs made within the last 45 days, therefore it is marked as inactive. If you would like to prevent this wiki from being closed, please start showing signs of activity here. If there are no signs of this wiki being used within the next 15 days, this wiki may be closed per the Dormancy Policy. This wiki will then be eligible for adoption by another user. If not adopted and still inactive 135 days from now, this wiki will become eligible for deletion. Please be sure to familiarize yourself with Miraheze's Dormancy Policy. If you are a bureaucrat, you can go to Special:ManageWiki and uncheck "inactive" yourself. If you have any other questions or concerns, please don't hesitate to ask at Stewards' noticeboard.

تجزیه اعداد

از 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;
}

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