سوال سوم Project Euler(همراه راه حل)

متن سوال:

عامل های اول عدد 13195 عبارتند از5, 7, 13 و 29.

بزرگترین عامل اول عدد600851475143 چیست؟

 

حل:

روش اول:

آیا واقعا می تونیم این سوال رو با شمردن تک تک حالات حل کنیم؟اگر وقت براتون مهم نیست می تونید!!!!

اینم کدش:

const long numm = 600851475143;

long largestFact = 0;

 

for (long i = 2; i < numm; i++) {

    if (numm % i == 0) { // It is a divisor

        bool isPrime = true;

        for (long j = 2; j < i; j++) {

            if (i % j == 0) {

                isPrime = false;

                break;

            }

        }

        if (isPrime) {

            largestFact = i;

        }

    }

}

روش دوم:

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

برای مثال مقسوم علیه های 24 عبارتند از 2و3و4و6و12.از طرفی جذر 24 حدودا 4.8 است پس ما اعداد را تا 4 چک می کنیم.

24/2 = 12
24/3 = 8
24/4 = 6

همون طور که می بینید تمام مقسوم علیه ها به دست اومد.خوب حالا باید چک کنیم کدومشون اول هستند وبین عامل های اول بزرگترین رو انتخاب کنیم.

اینم کدش:

const long long numm = 600851475143;

long largestFact = 0;

long[] factors = new long[2];

 

for (long i = 2; i * i < numm; i++) {

    if (numm % i == 0) { // It is a divisor

        factors[0] = i;

        factors[1] = numm / i;

 

        for (int k = 0; k < 2; k++) {

            bool isPrime = true;

            for (long j = 2; j * j <  factors[k]; j++) {

                if (factors[k] % j == 0) {

                    isPrime = false;

                    break;

                 }

             }

             if (isPrime && factors[k] > largestFact) {

                largestFact = factors[k];

            }

        }

    }

}

جواب برابر است با:

The largest primefactor of 600851475143 is: 6857

Solution took 15,625 ms

روش سوم:

ما اینو می دونیم که هر عدد بزرگ تر از یک رو می توان به صورت حاصل ضربی از اعداد اول نوشت.پس ما در این روش شروع می کنیم به خط زدن تک به تک عامل های اول یک عدد.

برای مثال ما می خوایم عامل های 12 رو پیدا کنیم برای این منظور

ابتدا 12 را تقسیم بر 2 می کنیم(اولین عدد اول)

حاصل 6 هست دو باره اونو بر 2 تقسیم می کنیم حاصل 3 هست 

پس حاصل تجزیه 12=2*2*3.

حالا ما تو کدمون تک تک عامل های اول رو که پیدا کردیم خط می کنیم(به ترتیب)تا به بزرگ ترین برسیم.

یکم کد رو بخونین درست می فهمین چطور شده!!!!

اینم کدش:

const long long numm = 600851475143;

long long newnumm = numm;

long long largestFact = 0;

 

int counter = 2;

while (counter * counter < newnumm) {

    if (newnumm % counter == 0) {

        newnumm = newnumm / counter;

        largestFact = counter;

    } else {

        counter++;

    }

}

if (newnumm > largestFact) { // the remainder is a prime number

    largestFact = newnumm;

}

 

The largest primefactor of 600851475143 is: 6857