المپیاد کامپیوتر

ترکیبیات,برنامه نویسی,گراف,الگوریتم , و کلا کامپیوتر

المپیاد کامپیوتر

ترکیبیات,برنامه نویسی,گراف,الگوریتم , و کلا کامپیوتر

المپیاد کامپیوتر
دنبال کنندگان ۳ نفر
این وبلاگ را دنبال کنید

سوال سوم 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

نظرات (۳)

  • نگار ابراهیمی
  • مرسـ ـی مـرســ ـی ؛؛)
  • نگار ابراهیمی
  • فقط مشکل آورفلو هنوزم هست؛ 600851475143 بیشتر از ظرفیت const long
    پاسخ:
    توی سی پلاس پلاس از long long استفاده کنید.
  • نگار ابراهیمی
  • آها.
    ولی تا نهایتاً سافیکس LL رو نذاشتم آخر عدد، کامپایلر آورفلو ارور میداد...
    ارسال نظر آزاد است، اما اگر قبلا در بیان ثبت نام کرده اید می توانید ابتدا وارد شوید.
    شما میتوانید از این تگهای html استفاده کنید:
    <b> یا <strong>، <em> یا <i>، <u>، <strike> یا <s>، <sup>، <sub>، <blockquote>، <code>، <pre>، <hr>، <br>، <p>، <a href="" title="">، <span style="">، <div align="">
    تجدید کد امنیتی