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

متن سوال:

2520کوچکترین عددی است که بر تمام اعداد یک تا ده بخش پذیر است.

کوچکترین عددی که بر تمام اعداد یک تا بیست بخش پذیر باشد چند است؟ 

حل:

روش اول:

مثل همیشه تک تک حالات رو میشماریم.چون باید بر 20 هم بخش پذیر باشد از 20 شروع می کنیم و بیستا بیستا میریم جلو.

اینم کدش:

int i = 20;

 

while (i %  2 != 0 || i %  3 != 0 || i %  4 != 0 || i %  5 != 0 ||

         i %  6 != 0 || i %  7 != 0 || i %  8 != 0 || i %  9 != 0 ||

         i % 10 != 0 || i % 11 != 0 || i % 12 != 0 || i % 13 != 0 ||

         i % 14 != 0 || i % 15 != 0 || i % 16 != 0 || i % 17 != 0 ||

         i % 18 != 0 || i % 19 != 0 || i % 20 != 0) {

    i += 20;

}

The smallest number dividable with all number 1-20 is 232792560

Solution took 125 ms

روش دوم :

ما می تونیم این سوالو  با دست هم می تونیم حساب کنید .

خوب اول که 2 رو باید داشته باشیم چون باید به 1 تا 20 بخشپذیر باشه.

بعدش باید به سه هم بخشپذیر باشه ولی الان نیست پس عدد رو ضرب در 3 می کنیم 3*2

بعد می رسیم به 4 عدد ما یکی 2 کم داره تا بر چهار بخشپذیر باشه پس 3*2*2

بعد ضرب در 5 می کنیم 5*3*2*2

خوب الان میرسیم به 6 ولی این جا نباید هیچ کاری کنیم چون عدد ما به به 6 بخشپذیره چون 3*2=6وما تو عددمون 3*2 رو داریم همینجور ادامه می دیم . تا به جواب برسیم .

اینم کدش:

long long sum=1;
for(int a=2;a<=20;a++){
if(sum%a!=0){
sum = sum*a;
cout<<a<<" ";
}
}
cout<<(sum/24);

در اینجا ما حاصل رو تقسیم به 24 کردیم چون وقتی میرسه به 4اونو ضرب در 2 نمی کنه ضرب در 4 می کنه ولی این تو زمانی که به 8 میرسیم خود به خود خنثی میشه ولی تو ی 16 به جای اینکه عدد رو ضرب در 2 کنه ضرب در 16 می کنه پس تا حالا یکی ضرب در 8(دو به توان سه) اضافی هست.

در مورد 9 هم همین طور یکی 3 اضافه داریم .پس باید تقسیم بر 24 (8*3)بکنیم.

حاصل برابر خواهد بود با:232792560