تجزیه اعداد

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

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